Edge-disjoint Hamilton cycles in random graphs

Abstract

We show that provided ${\log }^{50}n/n\le p\le 1-n^{-1/4}{\log }^{9}n$ we can with high probability find a collection of $\lfloor \delta (G)/2\rfloor$ edge-disjoint Hamilton cycles in $G\sim G_{n,p}$, plus an additional edge-disjoint matching of size $\lfloor n/2\rfloor$ if $\delta (G)$ is odd. This confirms, for the above range of $p$, a conjecture of Frieze and Krivelevich.

45 pages. This version incorporates comments from the referees

References in corpus (1)

• Hamilton decompositions of regular expanders: applications

Cited by in corpus (7)

• On prisms, Möbius ladders and the cycle space of dense graphs
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments
• On the number of Hamilton cycles in sparse random graphs
• On covering expander graphs by Hamilton cycles
• On the number of Hamilton cycles in pseudo-random graphs
• Optimal packings of Hamilton cycles in sparse random graphs