Bounds of a~number of leaves of spanning trees in graphs without triangles
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part III, Tome 391 (2011), pp. 5-17
Voir la notice de l'article provenant de la source Math-Net.Ru
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$.
@article{ZNSL_2011_391_a0,
author = {Bankevich A. V.},
title = {Bounds of a~number of leaves of spanning trees in graphs without triangles},
journal = {Zapiski Nauchnykh Seminarov POMI},
pages = {5--17},
publisher = {mathdoc},
volume = {391},
year = {2011},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZNSL_2011_391_a0/}
}
Bankevich A. V. Bounds of a~number of leaves of spanning trees in graphs without triangles. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part III, Tome 391 (2011), pp. 5-17. http://geodesic.mathdoc.fr/item/ZNSL_2011_391_a0/