On packing Hamilton cycles in ε-regular graphs

AbstractA graph G=(V,E) on n vertices is (α,ε)-regular if its minimal degree is at least αn, and for every pair of disjoint subsets S,T⊂V of cardinalities at least εn, the number of edges e(S,T) between S and T satisfies e(S,T)|S||T|-α⩽ε. We prove that if α⪢ε>0 are not too small, then every (α,ε)-regular graph on n vertices contains a family of (α/2-O(ε))n edge-disjoint Hamilton cycles. As a consequence we derive that for every constant 0<p