Hamiltonicity of graphs perturbed by a random regular graph

Abstract

We study Hamiltonicity and pancyclicity in the graph obtained as the union of a deterministic $n$-vertex graph $H$ with $\delta (H)\ge \alpha n$ and a random $d$-regular graph $G$, for $d\in \{1,2\}$. When $G$ is a random $2$-regular graph, we prove that a.a.s. $H\cup G$ is pancyclic for all $\alpha \in (0,1]$, and also extend our result to a range of sublinear degrees. When $G$ is a random $1$-regular graph, we prove that a.a.s. $H\cup G$ is pancyclic for all $\alpha \in (\sqrt{2}-1,1]$, and this result is best possible. Furthermore, we show that this bound on $\delta (H)$ is only needed when $H$ is `far' from containing a perfect matching, as otherwise we can show results analogous to those of random $2$-regular graphs. Our proofs provide polynomial-time algorithms to find cycles of any length.

arXiv commentTo appear in Random Structures and Algorithms