Hamilton cycles in regular graphs perturbed by a random 2-factor

2025/06/26 by Cicely, Henderson, Longbrake, Sean +2
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2506.21756

Abstract

In this paper, we prove that for each d ≥ 2, the union of a d-regular graph with a uniformly random 2-factor on the same vertex set is Hamiltonian with high probability. This resolves a conjecture by Draganić and Keevash for all values of d.

Citations

• Pósa rotation through a random permutation
• Hamiltonicity of expanders: optimal bounds and applications
• Hamiltonicity of graphs perturbed by a random regular graph
• Hamilton Cycles in Random Graphs: a bibliography
• Spanning trees in randomly perturbed graphs
• Bounded-degree spanning trees in randomly perturbed graphs
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Edge-disjoint Hamilton cycles in random graphs
• A survey on Hamilton cycles in directed graphs
• Some Theorems on Abstract Graphs

Related

• Hamiltonicity of graphs perturbed by a random regular graph
• Hamiltonicity in randomly perturbed hypergraphs
• Large connected strongly regular graphs are Hamiltonian
• Dirac's theorem for random regular graphs
• Hamilton Cycles in Random Lifts of Graphs