arXiv preprint ·
Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $\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 previously known ones for every $δ\ge7$; for $δ=8,9,10$ they are $0.5850\,n$, $0.6151\,n$ and $0.6413\,n$, and they are tabulated for $δ\le25$ at the end of the paper.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Boolean threshold functions, neuron capacity, and memory retrieval
Fast factorization in diagram monoids
Odd Cycle Transversal on $H$-free graphs
Construction of Partial Join Graphs with Perfect State Transfer in Shunt Decomposition-Based Quantum Walks
The Tight Upper Bound on the Number of Distinct Squares in Circular Words
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.