Hamiltonicity of graphs perturbed by a random regular graph

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