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

1 Introduction

• The largest guaranteed leaf count l(n, δ) is equivalent to n minus the largest connected domination number among the graphs in scope.The scope is connected n-vertex graphs with minimum degree at least δ.Source: §1 · p. 1
• The previous guarantee was 11/21 n (≈0.5238 n), inherited from Simarova’s degree-6 result; asymptotic results gave no explicit bound for degree 7.The asymptotic results involve unspecified terms and become meaningful only for large minimum degree.Source: §1 · p. 1
• 25200/46189 n (>0.5455 n) leaves are guaranteed when the minimum degree is at least 7.The bound is obtained constructively by a polynomial-time algorithm.Source: §1 · pp. 1–2
• The algorithm is analyzed for arbitrary minimum degree δ, yielding a recursion and explicit lower bounds on leaves for every δ.Theorem 1 is the δ = 7 case; bounds for 8 ≤ δ ≤ 25 improve the inherited 11/21 n bound.Source: §1 · p. 2
• Constructive guarantees are algorithmically relevant because finding a maximum-leaf spanning tree is NP-hard even for 4-regular graphs.Spanning trees with many leaves arise in network design and broadcasting, with internal vertices as routers and leaves as terminals.Source: §1 · p. 2

2 The algorithm

• The algorithm starts at a maximum-degree vertex, expands it into a star, and thereafter adds vertices through sequences of expansions.Expanding v adds all of its neighbors outside T as children, making v a non-leaf and those added vertices leaves.Source: §2 · p. 2
• In stages i=0,...,Iδ, the algorithm repeatedly applies E1i or E2i when available, and E3 is available only in stage 0.E1i expands a leaf and then a qualifying outside neighbor; E2i expands a leaf with enough outside neighbors; E3 expands a leaf, u, and then w.Source: §2 · p. 3
• Each stage uses at most n extensions, each found in polynomial time, and the final attachment step is linear.Every extension adds at least one vertex to T.Source: §2 · p. 3
• Attaching each remaining vertex to a neighboring leaf completes a spanning tree whose leaf count is at least yIδ.The remaining vertices become leaves, and the construction retains at least yIδ leaves from the final subtree.Source: §2 · p. 3

3 Analysis

• At each stage, every unadded vertex has only leaf neighbors in Ti; the stopping rules bound its neighbors in Zi and ensure at least δ−aδ+i+1 leaf neighbors.The analysis also bounds the number of Zi neighbors of each Yi vertex by βi.Source: §3 · p. 3
• Extension accounting bounds non-leaf growth relative to leaf growth, with separate inequalities for stage 0 and later stages.For an extension, the analysis uses upper bounds on Δx and lower bounds on Δy; it derives these from the E1i, E2i, and E3 cases.Source: §3 · pp. 3–4
• For minimum degree at least δ≥7, Theorem 7 guarantees a spanning tree with at least ηIδn leaves, so l(n,δ)≥ηIδn.The proof establishes yi≥ηin at every stage by induction.Source: §3 · p. 4
• The induction combines bounds on non-leaves and unprocessed vertices with n=xi+yi+zi to establish yi≥ηin at each stage.The proof starts with stage 0 and substitutes earlier inductive bounds into the recurrence.Source: §3 · pp. 4–5
• For δ=7, Corollary 8 sets aδ=5, I7=3, and (β0,β1,β2,β3)=(2,2,1,1), specializing Theorem 7 to prove Theorem 1.Source: §3 · p. 5
• The recursion’s tabulated lower bounds for 7≤δ≤25 each improve on 11/21, the bound inherited from minimum degree 6.Exact values for larger δ are omitted because the rationals have rapidly growing height.Source: §3 · pp. 5–6
• For δ≤6, the recursion gives weaker bounds than the known results, so Theorem 1 is stated for δ≥7.Source: §3 · p. 6
• The algorithm runs in polynomial time: each stage has at most n extensions, each extension is found in polynomial time, and final attachment is linear.Source: §3 · p. 6

• The Woodward Fund for Applied Mathematics at San José State University partially supported the work.Source: Funding · p. 6
• The fund is a gift from the estate of Mrs. Marie Woodward in memory of her son, Henry Teynham Woodward.Source: Funding · p. 6
• Henry Teynham Woodward was a Mathematics Department alumnus who worked with research groups at NASA Ames.Source: Funding · p. 6