Sogol Jahanbekam

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

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$,...