We prove that a connected graph of minimum degree 6 has a spanning tree such that at least \( \frac{11\ }{21} \) of its vertices are leaves.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. R. Griggs and M. Wu, “Spanning trees in graphs of minimum degree 4 or 5,” Discrete Math., 104, 167–183 (1992).
D. J. Kleitman and D. B. West, “Spanning trees with many leaves,” SIAM J. Discrete Math., 4, 99–106 (1991).
N. Alon, “Transversal numbers of uniform hypergraphs,” Graphs Combin., 6, 1–4 (1990).
D. V. Karpov, “Spanning trees with many leaves: new lower bounds in terms of the number of vertices of degree 3 and at least 4,” Zap. Nauchn. Semin. POMI, 406, 67–94 (2012).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 464, 2017, pp. 112–131.
Rights and permissions
About this article
Cite this article
Simarova, E.N. A Bound on the Number of Leaves in a Spanning Tree of a Connected Graph of Minimum Degree 6. J Math Sci 236, 542–553 (2019). https://doi.org/10.1007/s10958-018-4132-2
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10958-018-4132-2