Approximate Hamilton Decompositions of Random Graphs

Abstract

We show that if pn >> log n, the binomial random graph G_{n,p} has an approximate Hamilton decomposition. More precisely, we show that in this range G_{n,p} contains a set of edge-disjoint Hamilton cycles covering almost all of its edges. This is best possible in the sense that the condition that pn >> log n is necessary.

16 pages. This version incorporates comments from the referees

Cited by in corpus (1)

• Optimal packings of Hamilton cycles in sparse random graphs