|
Zapiski Nauchnykh Seminarov POMI, 2011, Volume 391, Pages 18–34
(Mi znsl4566)
|
|
|
|
This article is cited in 7 scientific papers (total in 7 papers)
Bounds of a number of leaves of spanning trees
A. V. Bankevicha, D. V. Karpovb a Saint-Petersburg State University, Saint-Petersburg, Russia
b St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences, St. Petersburg, Russia
Abstract:
We prove that every connected graph with $s$ vertices of degree not 2 has a spanning tree with at least $\frac14(s-2)+2$ leaves.
Let $G$ be a connected graph of girth $g$ with $v$ vertices. Let maximal chain of successively adjacent vertices of degree 2 in the graph $G$ does not exceed $k\ge1$. We prove that $G$ has a spanning tree with at least $\alpha_{g,k}(v(G)-k-2)+2$ leaves, where $\alpha_{g,k}=\frac{[\frac{g+1}2]}{[\frac{g+1}2](k+3)+1}$ for $k<g-2$; $\alpha_{g,k}(v(G)-k-2)+2$ for $k\ge g-2$.
We present infinite series of examples showing that all these bounds are exact.
Key words and phrases:
spanning tree, leaves, number of leaves.
Received: 15.09.2011
Citation:
A. V. Bankevich, D. V. Karpov, “Bounds of a number of leaves of spanning trees”, Combinatorics and graph theory. Part III, Zap. Nauchn. Sem. POMI, 391, POMI, St. Petersburg, 2011, 18–34; J. Math. Sci. (N. Y.), 184:5 (2012), 564–572
Linking options:
https://www.mathnet.ru/eng/znsl4566 https://www.mathnet.ru/eng/znsl/v391/p18
|
Statistics & downloads: |
Abstract page: | 283 | Full-text PDF : | 72 | References: | 35 |
|