Edge-disjoint Hamilton cycles in random graphs

2011/04/22 by Fiachra Knox, Knox, Fiachra, Daniela Kühn +3 · 5 citations
Computer Science · Mathematics · #05C45 #05C80 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1104.4412

openalex publication_date 2011/04/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Cited by

• On fractional triangle decompositions of random graphs
• Refined Absorption: A New Proof of the Existence Conjecture and its Applications to Extremal and Probabilistic Design Theory
• Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions
• Hamilton cycles in regular graphs perturbed by a random 2-factor
• The Hamilton cycle space of random graphs

Related

• Optimal packings of Hamilton cycles in sparse random graphs
• Minimum degree edge-disjoint Hamilton cycles in random directed graphs
• Edge-disjoint Hamilton cycles in graphs
• The probability of selecting k edge-disjoint Hamilton cycles in the complete graph
• Optimal covers with Hamilton cycles in random graphs