Optimal Packings of Hamilton Cycles in Graphs of High Minimum Degree

Abstract

We study the number of edge-disjoint Hamilton cycles one can guarantee in a sufficiently large graph G on n vertices with minimum degree δ=(1/2+α) n . For any constant α>0, we give an optimal answer in the following sense: let reg even ( n ,δ) denote the degree of the largest even-regular spanning subgraph one can guarantee in a graph on n vertices with minimum degree δ. Then the number of edge-disjoint Hamilton cycles we find equals reg even ( n ,δ)/2. The value of reg even ( n ,δ) is known for infinitely many values of n and δ. We also extend our results to graphs G of minimum degree δ ≥ n /2, unless G is close to the extremal constructions for Dirac's theorem. Our proof relies on a recent and very general result of Kühn and Osthus on Hamilton decomposition of robustly expanding regular graphs.

Locations

• arXiv (Cornell University) - View - PDF
• Combinatorics Probability Computing - View