|
Zapiski Nauchnykh Seminarov POMI, 2011, Volume 391, Pages 5–17
(Mi znsl4565)
|
|
|
|
This article is cited in 5 scientific papers (total in 5 papers)
Bounds of a number of leaves of spanning trees in graphs without triangles
Bankevich A. V. Saint-Petersburg State University, Saint-Petersburg, Russia
Abstract:
We prove that for every connected graph with girth at least $4$ and $s$ vertices of degree not $2$ there is a spanning tree with at least $\frac13(s-2)+2$ leaves. We describe series of examples showing that this bound is tight. This result, together with the bound for graphs with no limit on the girth (in such graphs one can construct a spanning tree with at least $\frac14(s-2)+2$ leaves) leads to the hypothesis that for a graph with girth at least $g$, there exists a spanning tree with at least $\frac{g-2}{2g-2}(s-2)+2$ leaves. We prove that this conjecture fails for $g\ge10$ and the bound cannot exceed $\frac7{16}s+\frac12$.
Key words and phrases:
spanning tree, leaves, number of leaves.
Received: 28.09.2011
Citation:
Bankevich A. V., “Bounds of a number of leaves of spanning trees in graphs without triangles”, Combinatorics and graph theory. Part III, Zap. Nauchn. Sem. POMI, 391, POMI, St. Petersburg, 2011, 5–17; J. Math. Sci. (N. Y.), 184:5 (2012), 557–563
Linking options:
https://www.mathnet.ru/eng/znsl4565 https://www.mathnet.ru/eng/znsl/v391/p5
|
Statistics & downloads: |
Abstract page: | 208 | Full-text PDF : | 46 | References: | 40 |
|