Geodesic
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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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},
     year = {2011},
     volume = {391},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2011_391_a0/}
}
TY  - JOUR
AU  - Bankevich A. V.
TI  - Bounds of a number of leaves of spanning trees in graphs without triangles
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2011
SP  - 5
EP  - 17
VL  - 391
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2011_391_a0/
LA  - ru
ID  - ZNSL_2011_391_a0
ER  - 
%0 Journal Article
%A Bankevich A. V.
%T Bounds of a number of leaves of spanning trees in graphs without triangles
%J Zapiski Nauchnykh Seminarov POMI
%D 2011
%P 5-17
%V 391
%U http://geodesic.mathdoc.fr/item/ZNSL_2011_391_a0/
%G ru
%F 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/

[1] A. V. Bankevich, D. V. Karpov, “Otsenki kolichestva visyachikh vershin v ostovnykh derevyakh”, Zap. nauchn. semin. POMI, 391, 2011, 18–34 | MR

[2] J. A. Storer, “Constructing full spanning trees for cubic graphs”, Inform. Process. Lett., 13:1 (1981), 8–11 | DOI | MR | Zbl

[3] J. R. Griggs, D. J. Kleitman, A. Shastri, “Spanning trees with many leaves in cubic graphs”, J. Graph Theory, 13:6 (1989), 669–695 | DOI | MR | Zbl

[4] D. J. Kleitman, D. B. West, “Spanning trees with many leaves”, SIAM J. Discrete Math., 4:1 (1991), 99–106 | DOI | MR | Zbl

[5] J. R. Griggs, M. Wu, “Spanning trees in graphs of minimum degree 4 or 5”, Discr. Math., 104 (1992), 167–183 | DOI | MR | Zbl

[6] N. Alon, “Transversal numbers of uniform hypergraphs”, Graphs and Combinatorics, 6 (1990), 1–4 | DOI | MR | Zbl

[7] G. Ding, T. Johnson, P. Seymour, “Spanning trees with many leaves”, J. Graph Theory, 37:4 (2001), 189–197 | DOI | MR | Zbl

[8] Y. Caro, D. B. West, R. Yuster, “Connected domination and spanning trees with many leaves”, SIAM J. Discrete Math., 13:2 (2000), 202–211 | DOI | MR

[9] P. S. Bonsma, “Spanning trees with many leaves in graphs with minimum degree three”, SIAM J. Discrete Math., 22:3 (2008), 920–937 | DOI | MR | Zbl

[10] P. S. Bonsma, F. Zickfeld, “Spanning trees with many leaves in graphs without diamonds and blossoms”, LATIN 2008: Theoretical Informatics, Lect. Notes Comput. Sci., 4957, Springer-Verlag, Berlin, 2008, 531–543 | DOI | MR | Zbl

[11] N. V. Gravin, “Postroenie ostovnogo dereva grafa s bolshim kolichestvom listev”, Zap. nauchn. semin. POMI, 381, 2010, 31–46 | MR

[12] D. V. Karpov, “Ostovnoe derevo s bolshim kolichestvom visyachikh vershin”, Zap. nauchn. semin. POMI, 381, 2010, 78–87 | MR

[13] F. Kharari, Teoriya grafov, Mir, Moskva, 1973 | MR

[14] Béla Bolobás, Extremal graph Theory, Academic Press, 1978 | MR | Zbl