Geodesic
Spanning trees with many leaves: new lower bounds in terms of number of vertices of degree 3 and at least 4
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part V, Tome 406 (2012), pp. 31-66 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 3 and $t$ vertices of degree at least 4 has a spanning tree with $\frac25t+\frac15s+\alpha$ leaves, where $\alpha\ge\frac85$. Moreover, $\alpha\ge2$ for all graphs besides three exclusions. All exclusion are regular graphs of degree 4, they are explicitly described in the paper. We present an infinite series of graphs, containing only vertices of degrees 3 and 4, for which the maximal number of leaves in a spanning tree is equal for $\frac25t+\frac15s+2$. Therefore we prove that our bound is tight. 
@article{ZNSL_2012_406_a2,
     author = {D. V. Karpov},
     title = {Spanning trees with many leaves: new lower bounds in terms of number of vertices of degree~3 and at least~4},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {31--66},
     year = {2012},
     volume = {406},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_406_a2/}
}
TY  - JOUR
AU  - D. V. Karpov
TI  - Spanning trees with many leaves: new lower bounds in terms of number of vertices of degree 3 and at least 4
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 31
EP  - 66
VL  - 406
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_406_a2/
LA  - ru
ID  - ZNSL_2012_406_a2
ER  - 
%0 Journal Article
%A D. V. Karpov
%T Spanning trees with many leaves: new lower bounds in terms of number of vertices of degree 3 and at least 4
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 31-66
%V 406
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_406_a2/
%G ru
%F ZNSL_2012_406_a2
D. V. Karpov. Spanning trees with many leaves: new lower bounds in terms of number of vertices of degree 3 and at least 4. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part V, Tome 406 (2012), pp. 31-66. http://geodesic.mathdoc.fr/item/ZNSL_2012_406_a2/

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

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

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

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

[5] N. Martinov, “A recursive characterization of the 4-connected graphs”, Discrete Math., 84:1 (1990), 105–108 | 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, Lecture Notes Comput. Sci., 4957, Springer, Berlin, 2008 | MR | Zbl

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

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

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