{"id":"arxiv/2609.30354","url":"https://arxiv.org/abs/2609.30354","tags":["cs.DS","math.CO"],"score":0,"title":"Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7","domain":"cs.DS","source":"arxiv","authors":["Sogol Jahanbekam"],"reviews":0,"subject":"cs.DS","summary":"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 $δ$, and yield a recursion that gives an explicit lower bound on the number of leaves for every $δ$. The resulting bounds improve all…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{}}