Edge-disjoint hamilton cycles in random graphs
Research output: Contribution to journal › Article
Colleges, School and Institutes
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.
|Number of pages||49|
|Journal||Random Structures and Algorithms|
|Early online date||2 Jul 2013|
|Publication status||Published - 1 May 2015|