Pancyclicity of randomly perturbed digraph
Authors: Ren Zelin , Hou Xinmin ,   School of Cyber Science and Technology, University of Science and Technology of China, Hefei 230022，China,   Wu Wen-Tsun Key Laboratory of Mathematics, School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, China
Published: May 2022

Dirac’s theorem states that if a graph <i>G</i> on <i>n</i> vertices has a minimum degree of at least <inline-formula><tex-math id="M1">\begin{document}$\displaystyle \frac{n}{2}$\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M1.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M1.png"/></alternatives></inline-formula>, then <i>G</i> contains a Hamiltonian cycle. Bohman et al. introduced the random perturbed graph model and proved that for any constant <inline-formula><tex-math id="M2">\begin{document}$ \alpha > 0 $\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M2.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M2.png"/></alternatives></inline-formula> and a graph <i>H</i> with a minimum degree of at least <inline-formula><tex-math id="M3">\begin{document}$ \alpha n $\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M3.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M3.png"/></alternatives></inline-formula>, there exists a constant <i>C</i> depending on <i>α</i> such that for any <inline-formula><tex-math id="M4">\begin{document}$p \geqslant \dfrac{C}{n}$\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M4.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M4.png"/></alternatives></inline-formula>, <inline-formula><tex-math id="M5">\begin{document}$H \cup {G_{n,p}}$\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M5.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M5.png"/></alternatives></inline-formula> is asymptotically almost surely (a.a.s.) Hamiltonian. In this study, the random perturbed digraph model is considered, and we show that for all <inline-formula><tex-math id="M6">\begin{document}$\alpha = \omega \left( {{{\left( {\dfrac{{\log n}}{n}} \right)}^{{\textstyle{1 \over 4}}}}} \right)$\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M6.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M6.png"/></alternatives></inline-formula> and <inline-formula><tex-math id="M7">\begin{document}$d \in \{ 1,2\}$\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M7.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M7.png"/></alternatives></inline-formula>, the union of a digraph on <i>n</i> vertices with a minimum degree of at least <inline-formula><tex-math id="M8">\begin{document}$ \alpha n $\end{document}</tex-math><alternatives><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M8.jpg"/><graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="JUST-2021-0208_M8.png"/></alternatives></inline-formula> and a random <i>d</i>-regular digraph on <i>n</i> vertices is a.a.s. pancyclic. Moreover, a polynomial-time algorithm is proposed to find cycles of any length in such a digraph.