Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7
In the authors' words
We give a polynomial-time algorithm that constructs, in every connected -vertex graph of minimum degree at least , a spanning tree with at least leaves. No bound specific to minimum degree was known: the best bound available for this class was , inherited from Simarova's theorem for minimum degree~. The algorithm and its analysis are carried out for an arbitrary minimum degree , and yield a recursion that gives an explicit lower bound on the number of leaves for every . The resulting bounds improve all previously known ones for every ; for they are , and , and they are tabulated for at the end of the paper.
Main resultThe abstract does not state a limitation.
Appeared: Monday, September 28. arXiv. Preprint, not yet peer-reviewed.