Optimal covers with Hamilton cycles in random graphs

Dan Hefetz*, Daniela Kühn, John Lapinskas, Deryk Osthus

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


A packing of a graph G with Hamilton cycles is a set of edge-disjoint Hamilton cycles in G. Such packings have been studied intensively and recent results imply that a largest packing of Hamilton cycles in Gn,p a.a.s. has size {box drawings light up and right}δ(Gn,p)/2{box drawings light up and left}. Glebov, Krivelevich and Szabó recently initiated research on the 'dual' problem, where one asks for a set of Hamilton cycles covering all edges of G. Our main result states that for log (Formula presented.), a.a.s. the edges of Gn,p can be covered by {box drawings light up and left}{increment}(Gn,p)/2{box drawings light up and left} Hamilton cycles. This is clearly optimal and improves an approximate result of Glebov, Krivelevich and Szabó, which holds for p ≤ n-1+ε. Our proof is based on a result of Knox, Kühn and Osthus on packing Hamilton cycles in pseudorandom graphs.

Original languageEnglish
Pages (from-to)573–596
Issue number5
Early online date23 Jun 2014
Publication statusPublished - Oct 2014

ASJC Scopus subject areas

  • Computational Mathematics
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Optimal covers with Hamilton cycles in random graphs'. Together they form a unique fingerprint.

Cite this