Geodesic
Lower bounds on the number of leaves in spanning trees
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VIII, Tome 450 (2016), pp. 62-73
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Let $G$ be a connected graph on $n\ge2$ vertices with girth at least $g$. Let maximal chain of successively adjacent vertices of degree 2 in the graph $G$ does not exceed $k\ge1$. Denote by $u(G)$ the maximal number of leaves in a spanning tree of $G$. We prove, that $u(G)\ge\alpha_{g,k}(v(G)-k-2)+2$, where $\alpha_{g,1}=\frac{[\frac{g+1}2]}{4[\frac{g+1}2]+1}$ and $\alpha_{g,k}=\frac1{2k+2}$ for $k\ge2$. We present infinite series of examples showing that all these bounds are tight. 
@article{ZNSL_2016_450_a4,
     author = {D. V. Karpov},
     title = {Lower bounds on the number of leaves in spanning trees},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {62--73},
     year = {2016},
     volume = {450},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a4/}
}
TY  - JOUR
AU  - D. V. Karpov
TI  - Lower bounds on the number of leaves in spanning trees
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2016
SP  - 62
EP  - 73
VL  - 450
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a4/
LA  - ru
ID  - ZNSL_2016_450_a4
ER  - 
%0 Journal Article
%A D. V. Karpov
%T Lower bounds on the number of leaves in spanning trees
%J Zapiski Nauchnykh Seminarov POMI
%D 2016
%P 62-73
%V 450
%U http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a4/
%G ru
%F ZNSL_2016_450_a4
D. V. Karpov. Lower bounds on the number of leaves in spanning trees. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VIII, Tome 450 (2016), pp. 62-73. http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a4/

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

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

[10] F. Kharari, Teoriya grafov, Mir, Moskva, 1973

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

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

[13] A. V. Bankevich, D. V. Karpov, “Otsenki kolichestva visyachikh vershin v ostovnykh derevyakh”, J. Math. Sci., 184:5 (2012), 564–572 | DOI | Zbl

[14] A. V. Bankevich, “Otsenki kolichestva visyachikh vershin v ostovnykh derevyakh v grafakh bez treugolnikov”, J. Math. Sci., 184:5 (2012), 557–563 | DOI | Zbl