Edge-disjoint hamilton cycles in random graphs

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

Abstract

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.

Details

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

Keywords

  • Hamilton cycles, Packings, Random graphs