Geodesic
Bounds of a number of leaves of spanning trees
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part III, Tome 391 (2011), pp. 18-34 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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; $\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. 
@article{ZNSL_2011_391_a1,
     author = {A. V. Bankevich and D. V. Karpov},
     title = {Bounds of a~number of leaves of spanning trees},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {18--34},
     year = {2011},
     volume = {391},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2011_391_a1/}
}
TY  - JOUR
AU  - A. V. Bankevich
AU  - D. V. Karpov
TI  - Bounds of a number of leaves of spanning trees
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2011
SP  - 18
EP  - 34
VL  - 391
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2011_391_a1/
LA  - ru
ID  - ZNSL_2011_391_a1
ER  - 
%0 Journal Article
%A A. V. Bankevich
%A D. V. Karpov
%T Bounds of a number of leaves of spanning trees
%J Zapiski Nauchnykh Seminarov POMI
%D 2011
%P 18-34
%V 391
%U http://geodesic.mathdoc.fr/item/ZNSL_2011_391_a1/
%G ru
%F ZNSL_2011_391_a1
A. V. Bankevich; D. V. Karpov. Bounds of a number of leaves of spanning trees. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part III, Tome 391 (2011), pp. 18-34. http://geodesic.mathdoc.fr/item/ZNSL_2011_391_a1/

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

[2] 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

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

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

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

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

[7] 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

[8] 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

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

[10] Journal of Mathematical Sciences | MR

[11] Journal of Mathematical Sciences | MR

[12] F. Kharari, Teoriya grafov, Mir, M., 1973 ; F. Harary, Graph theory, 1969 | MR | MR