For pseudorandom graphs with large spectral gap, every subgraph with minimum degree above d/2 is Hamiltonian, and the whole edge set can be packed into, and covered by, about d/2 Hamilton cycles.
Approximate path decompositions of regular graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We show that the edges of any $d$-regular graph can be almost decomposed into paths of length roughly $d$, giving an approximate solution to a problem of Kotzig from 1957. Along the way, we show that almost all of the vertices of a $d$-regular graph can be partitioned into $n/(d+1)$ paths, asymptotically confirming a conjecture of Magnant and Martin from 2009.
citation-role summary
background 1
citation-polarity summary
fields
math.CO 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions
For pseudorandom graphs with large spectral gap, every subgraph with minimum degree above d/2 is Hamiltonian, and the whole edge set can be packed into, and covered by, about d/2 Hamilton cycles.