Geodesic
Spanning trees with many leaves: lower bounds in terms of number of vertices of degree 1, 3 and at least 4
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part V, Tome 406 (2012), pp. 67-94
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 1 and 3 and $t$ vertices of degree at least 4 has a spanning tree with at least $\frac13t+\frac14s+\frac32$ leaves. We present an infinite series of graphs showing that our bound is tight. 
@article{ZNSL_2012_406_a3,
     author = {D. V. Karpov},
     title = {Spanning trees with many leaves: lower bounds in terms of number of vertices of degree~1, 3 and at least~4},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {67--94},
     year = {2012},
     volume = {406},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_406_a3/}
}
TY  - JOUR
AU  - D. V. Karpov
TI  - Spanning trees with many leaves: lower bounds in terms of number of vertices of degree 1, 3 and at least 4
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 67
EP  - 94
VL  - 406
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_406_a3/
LA  - ru
ID  - ZNSL_2012_406_a3
ER  - 
%0 Journal Article
%A D. V. Karpov
%T Spanning trees with many leaves: lower bounds in terms of number of vertices of degree 1, 3 and at least 4
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 67-94
%V 406
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_406_a3/
%G ru
%F ZNSL_2012_406_a3
D. V. Karpov. Spanning trees with many leaves: lower bounds in terms of number of vertices of degree 1, 3 and at least 4. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part V, Tome 406 (2012), pp. 67-94. http://geodesic.mathdoc.fr/item/ZNSL_2012_406_a3/

[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 Combinator., 6 (1990), 1–4 | DOI | MR | Zbl

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

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

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

[8] 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, Berlin, 2008, 531–543 | DOI | MR | Zbl

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

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

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

[12] A. V. Bankevich, “Otsenki kolichestva visyachikh vershin v ostovnykh derevyakh v grafakh bez treugolnikov”, Zap. nauchn. semin. POMI, 391, 2011, 5–17 | MR

[13] D. V. Karpov, “Ostovnye derevya s bolshim kolichestvom visyachikh vershin: novye nizhnie otsenki cherez kolichestvo vershin stepenei 3 i 4”, Zap. nauchn. semin. POMI, 406, 2012, 31–66 | MR