Interpolation theorem for the number of pendant vertices of connected spanning subgraphs of equal size
type: Item
instance of: scholarly article
title: Interpolation theorem for the number of pendant vertices of connected spanning subgraphs of equal size
zbMATH Open document ID: 0576.05057
DOI: 10.1016/0012-365X(84)90061-X
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: Let G(p,q) be a connected graph. Following the notation of the author, a connected spanning subgraph of G having i edges and j pendant vertices (j\(\geq 1)\) is called an \(S_ 0(i,j)\)-subgraph, and a connected spanning subgraph with i mutually edge-disjoint cycles, j pendant vertices, and \(p+i-1\) edges is called an \(S_ 1(i,j)\)-subgraph. Two interpolation theorems are obtained. If G has \(S_ 0(i,k)\)-subgraphs for \(k=m\) and \(k=n\), where \(m<n\), then it has \(S_ 0(i,k)\)-subgraphs for each k, \(m<k<n\). If, in addition, G has at least \(2(p+i-1)\) edges, then the analogous result holds for \(S_ 1(i,j)\)-subgraphs. The corresponding interpolation theorem for spanning trees was proved constructively by \textit{S. Schuster} [J. Graph Theory 7, 203-208 (1983; Zbl 0482.05032)].
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 3920531
zbMATH Keywords: connected spanning subgraph
zbMATH Keywords: interpolation theorems
author: Curtiss Barefoot
MaRDI profile type: Publication
cites work: Interpolation theorem for the number of end‐vertices of spanning trees
description: scientific article; zbMATH DE number 3920531