Edge-disjoint hamilton cycles in random graphs

Research output: Contribution to journalArticlepeer-review

26 Citations (Scopus)


We show that provided log50n/n≤p≤1-n-1/4log9n we can with high probability find a collection of ⌊δ(G)/2⌋ edge-disjoint Hamilton cycles in G~Gn,p, plus an additional edge-disjoint matching of size ⌊n/2⌋ if δ(G) is odd. This is clearly optimal and confirms, for the above range of p, a conjecture of Frieze and Krivelevich.

Original languageEnglish
Pages (from-to)397-445
Number of pages49
JournalRandom Structures and Algorithms
Issue number3
Early online date2 Jul 2013
Publication statusPublished - 1 May 2015


  • Hamilton cycles
  • Packings
  • Random graphs

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Software
  • Mathematics(all)
  • Applied Mathematics


Dive into the research topics of 'Edge-disjoint hamilton cycles in random graphs'. Together they form a unique fingerprint.

Cite this