Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7

Abstract

We give a polynomial-time algorithm that constructs, in every connected $n$-vertex graph of minimum degree at least $7$, a spanning tree with at least $\frac{25200}{46189}n>0.5455\,n$ leaves. No bound specific to minimum degree $7$ was known: the best bound available for this class was $\frac{11}{21}n\approx0.5238\,n$, inherited from Simarova's theorem for minimum degree~$6$. The algorithm and its analysis are carried out for an arbitrary minimum degree $\delta$, and yield a recursion that gives an explicit lower bound on the number of leaves for every $\delta$. The resulting bounds improve all previously known ones for every $\delta\ge7$; for $\delta=8,9,10$ they are $0.5850\,n$, $0.6151\,n$ and $0.6413\,n$, and they are tabulated for $\delta\le25$ at the end of the paper.