Pancyclicity of randomly perturbed digraph

Dirac’s theorem states that if a graph G on n vertices has a minimum degree of at least $\displaystyle \frac{n}{2}$, then G contains a Hamiltonian cycle. Bohman et al. introduced the random perturbed graph model and proved that for any constant $ \alpha > 0 $ and a graph H with a minimum degree of at least $ \alpha n $, there exists a constant C depending on α such that for any $p \geqslant \dfrac{C}{n}$, $H \cup {G_{n,p}}$ is asymptotically almost surely (a.a.s.) Hamiltonian. In this study, the random perturbed digraph model is considered, and we show that for all $\alpha = \omega \left( {{{\left( {\dfrac{{\log n}}{n}} \right)}^{{\textstyle{1 \over 4}}}}} \right)$ and $d \in \{ 1,2\}$, the union of a digraph on n vertices with a minimum degree of at least $ \alpha n $ and a random d-regular digraph on n vertices is a.a.s. pancyclic. Moreover, a polynomial-time algorithm is proposed to find cycles of any length in such a digraph.