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 \fracn2, 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 \dfracCn, 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 nn \right)^\textstyle1 \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.