A bound on the number of leaves in a spanning tree of a connected graph of minimal degree 6
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IX, Tome 464 (2017), pp. 112-131
Citer cet article
Voir la notice du chapitre de livre provenant de la source Math-Net.Ru
It is proved, that a connected graph of minimal degree 6 has a spanning tree, such that at least $\frac{11}{21}$ of its vertices are leaves.
[1] J. R. Griggs, M. Wu, “Spanning trees in graphs of minimum degree $4$ or $5$”, Discrete Math., 104 (1992), 167–183 | 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] N. Alon, “Transversal numbers of uniform hypergraphs”, Graphs and Combinatorics, 6 (1990), 1–4 | DOI | MR | Zbl
[4] D. V. Karpov, “Ostovnye derevya s bolshim kolichestvom visyachikh vershin: novye nizhnie otsenki cherez kolichestvo vershin stepenei $3$ i ne menee $4$”, Zap. nauchn. semin. POMI, 406, 2012, 67–94 | MR