PreprintCC BY 4.0arXiv
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 25200/46189n>0.5455 n leaves. No bound specific to minimum degree $7$ was known: the best bound available for this class was 11/21n≈0.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 previously known ones for every δ≥7; for δ=8,9,10 they are 0.5850 n, 0.6151 n and 0.6413 n, and they are tabulated for δ≤25 at the end of the paper.
Related
- Hamiltonian graphs with prescribed minimum degree and no near-spanning cycles
- Spectral radius and edge-disjoint spanning trees of graphs with edge connectivity
- Maximum and Minimum Spectral Radii in an Exceptional Family for Edge-Disjoint Spanning Trees
- On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
- Maximum number of spanning trees in bipartite graphs with a given diameter
BibTeX
@misc{jahanbekam2026spanning,
title = {{Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7}},
author = {Sogol Jahanbekam},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30354},
eprint = {2609.30354},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30354},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7
AU - Sogol Jahanbekam
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.30354
UR - https://arxiv.org/abs/2609.30354
AB - 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 25200/46189n>0.5455 n leaves. No bound specific to minimum degree $7$ was known: the best bound available for this class was 11/21n≈0.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 previously known ones for every δ≥7; for δ=8,9,10 they are 0.5850 n, 0.6151 n and 0.6413 n, and they are tabulated for δ≤25 at the end of the paper.
ER -