Pancyclicity of randomly perturbed digraph

1.   Introduction

In graph theory, Dirac’s famous theorem^[1] 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. Moreover, if G is not a completely balanced bipartite graph $K_{\frac{n}{2},\frac{n}{2}}$, then the result can be strengthened such that G is pancyclic; i.e., G contains cycles of all lengths from 3 to n.

The study of random structures is a thriving field in the graph theory. This implies that we can generate a graph according to a certain distribution, and the probability that the graph satisfies some property is considered. A well-known model is the Erdös-Rényi random graph $G_{n,\;p}$, which is a graph of n vertices whose edges appear individually independent with probability p. It was shown in Ref. [2] that if $p\geqslant (1+\varepsilon)\dfrac{\log n}{n}$, then $G_{n,p}$ is asymptotically almost surely (a.a.s.) Hamiltonian.

In 2003, Bohman et al.^[3] introduced an random perturbed graph model. This is a combination of extremal problems and the study of random structures. In this model, we consider a graph H, whose minimum degree is bounded by $\delta(H)\geqslant\alpha n$, and a random graph G according to a certain distribution. The goal is to determine whether $H\cup G$ a.a.s satisfies certain properties. Bohman et al.^[3] examined the problem of Hamiltonicity and proved that for any constant $\alpha>0$ and a graph H with $\delta(H)\geqslant\alpha n$, there exists a constant C depending on α such that for any $p\geqslant \dfrac{C}{n}$, $H\cup G_{n,p}$ is a.a.s. Hamiltonian. Krivelevich et al.^[4] generalized Hamiltonicity to pancyclicity, and Hahn-Klimroth et al.^[5] showed that the constant α can be a function that tends to 0, where n tends to infinity. Hamiltonicity has also been studied in randomly perturbed digraphs^{[3, 4]}, hypergraphs^{[4, 6, 7, 8]}, and subgraphs of the hypercube^[9]. Many other properties of this model have also been studied. For example, the existence of powers of Hamiltonian cycles^{[10, 11]}, F-factor^{[12, 13]}, and general bounded degree spanning graphs^[11]. In all these cases, the results significantly improved the bounds provided by the traditional random graph model. Recently, Espuny Díaz and Girão^[14] considered Hamiltonicity in graphs perturbed by a random regular graph.

In this study, we consider a randomly perturbed digraph model, i.e., the Hamiltonicity and pancyclicity of $H\cup D$, where H is a digraph on n vertices with $\delta(H)\geqslant\alpha n$, and D is a random d-regular digraph for some $d\in\mathbb{N}$. Cooper et al.^[15] proved that for all $d\geqslant 3$, the random d-regular digraph is a.a.s. Hamiltonian. Hence, we only consider the case when $d\in\{1,2\}$. Furthermore, the main result is as follows:

Theorem 1.1. Let $\alpha=\omega\left( {\left( {\dfrac{\log n}{n}} \right)^{\tfrac{1}{4}}} \right)$ and $d\in\{1,2\}$ and let H be a graph of n vertices with $\delta(H)\geqslant \alpha n$. Then, a.a.s. $H\cup D$ is pancyclic, where D is a random d-regular digraph on n vertices.

The remainder of this paper is organized as follows. In Section 2, some notation and lemmas are presented. Proof of Theorem 1.1 is presented in Section 3. Finally, in Section 4, we present an open problem.

2.   Preliminaries

2.1   Notation

For $m,n\in\mathbb{N}$, we denote $[m, n]:=\{m, m+1,\cdots,n\}$ and $[n]= [1,n]$. For the asymptotic notations, we use the standard ${\cal{O}}$ notation and assume that the functions are nonnegative.

Throughout this paper, the term digraph denotes to a simple directed graph. For any digraph D of n vertices, we implicitly assume that $V(D)=[n]$.

Given a digraph $D=(V,E)$ and any vertex $v\in V$, we let $N_D^+(v):=\{w\in V\mid (v,w)\in E\}$ be the out-neighbor set of v, and $N_D^-(v):=\{w\in V\mid (w,v)\in E\}$ be the in-neighbor set of v. Additionally, we denote its out-degree in D by $d_D^+(v):=|N_D^+(v)|$ and its in-degree by $d_D^-(v):=|N_D^-(v)|$. The maximum out-degree of D is defined as $\Delta^+(D):=\max_{v\in V}d_D^+(v)$ and maximum in-degree of D is defined as $\Delta^-(D):=\max_{v\in V}d_D^-(v)$. Similarly, we can define the minimum out-degree $\delta^+(D)$ and minimum in-degree $\delta^-(D)$. The maximum degree of D is $\Delta(D)= \max\{\Delta^+(D),\Delta^-(D)\}$, and similarly, we can define the minimum degree of a digraph D by $\delta(D)=\min\{\delta^+(D),\delta^-(D)\}$. We can state that digraph D is d-regular if $\Delta(D)=\delta(D)=d$.

Given a digraph $D=(V,E)$ and vertex subset $V^*\subset V$, let $E(V^*)=\{(x,y)\in E\mid x,y\in V^*\}$. The induced subgraph of $V^*$ is defined as $D[V^*]=(V^*,E(V^*))$. We write $D\setminus V^*=D[V\setminus V^*]$. Given another digraph $D'$, $D\cup D'=(V(D)\cup V(D'), E(D)\cup E(D'))$ and $D'\subset D$ if $V(D')\subset V(D)$ and $E(D')\subset E(D')$. Let $E'\subset V\times V$ be a set of edges, and let $D\setminus E'=(V,E\setminus E')$ and $D\cup E'=(V,E\cup E').$

A directed path $P=v_1v_2\cdots v_\ell$ is the digraph $P=(\{v_i\mid i\in [\ell]\},\{(v_i,v_{i+1})\mid i\in [\ell-1]\})$, where all vertices $\{v_i\mid i\in [\ell]\}$ are distinct. Furthermore, degenerated cases can exist in which P is an isolated vertex. We can state that $P\subset D$ is the maximal directed path if $N_D^-(v_1),N_D^+(v_\ell)\subset V(P)$. A directed cycle $C=v_1v_2\cdots v_\ell v_1$ is the digraph $C=(\{v_i\mid i\in [\ell]\},\{(v_i,v_{i+1}) \mid i\in [\ell-1]\}\cup\{(v_\ell,v_1)\})$, where all vertices $\{v_i\mid i\in [\ell]\}$ are distinct.

2.2   Configuration model

The configuration model is the most useful tool to examine random regular graphs or digraphs, and it was introduced by Bollobás^[16].The configuration model provides a process that uniformly generates a random regular graph. We used the model to generate a random 1-regular digraph. The process is as follows. For any $i\in [n]$, we consider a set of two vertices, $x_i$ and $y_i$. Then, we select a uniformly random perfect matching M covering set $\{x_i\mid i\in [n]\}\cup\{y_i\mid i\in [n]\}$ using only (undirected) edges of the form $x_iy_j$ for some $i,j\in [n]$. Now, we generate a 1-regular digraph $D=(V,E)$, where, for each edge $x_iy_j\in M$, a directed edge $(i,j)$ is added to E.

Whenever we produce a random 1-regular digraph D following the process above, we use ${\cal{C}}_{n,1}$ to denote the distribution of D, and ${\cal{C}}^*_{n,1}$ to denote the distribution of the corresponding perfect matching M. We state that perfect matching M that generates D is a configuration. We observe that for any 1-regular digraph D, exactly one configuration M exists that generates D.

Suppose we have two configurations $M_1$ and $M_2$. We state $M_1\sim M_2$ if there exist two edges $x_iy_j$ and $x_ky_l$ in $M_1$ such that $M_2=(M_1\setminus\{x_iy_j,x_ky_l\})\cup\{x_iy_l,x_ky_j\}$. The following lemma bounds the probability that certain variable in the configurations deviate from their expectation.

Lemma 2.1. Let $c>0$ and let X be a random variable on ${\cal{C}}^*_{n,1}$ such that for every pair of configurations $M_1\sim M_2$, we always have $|X(M_1)-X(M_2)|\leqslant c$. Then, for all $t\in\mathbb{N}$, we have

Proof. It should be noted that if we ignore the orientation, the graph generated by configuration $M\in{\cal{C}}^*_{n,1}$ is a 2-regular undirected graph. Díaz and Girão^{[14, Lemma 2.1]} proved that

under the same conditions provided in this lemma. The proof is complete, and this lemma can be considered as a directed version of Lemma 2.1 in Ref. [14].

When we sample a random 1-regular digraph following the process above, we observed that the obtained digraph contains loops. However, by conditioning the event that D is a 1-regular digraph without a loop, this type of a graph is a uniformly random 1-regular simple digraph. The configuration of a loopless 1-regular simple digraph can be viewed as a derangement of $[n]$. Therefore, by considering the derangement problem, we have

Lemma 2.2. Let D be a random 1-regular digraph of n vertices generated by the process above. If $n\geqslant 3$, then $P(D$ contains no loops $)\geqslant \dfrac{1}{3} > 0$.

Proof. There are $n!$ potential configurations for generating a 1-regular graph on n vertices. A configuration can be viewed as a permutation σ on $[n]$, i.e., $x_iy_j\in M\Leftrightarrow \sigma(i)=j$. In this manner, D contains no loop, indicating that σ is a derangement of $[n]$. Hence, we have $n! \displaystyle \sum_{i=0}^{n}\dfrac{(-1)^i}{i!}$ possible choices for σ. Therefore, the probability

2.3   Properties of random 1-regular digraph

Let D be a 1-regular digraph of n vertices. Thus, the underlying graph G of D is 2-regular. It should be noted that the strongly connected component of D is a directed cycle, which is also a component of G. Díaz and Girão showed that G has a maximum of $\log^2 n$ components^{[14, Lemma 3.1(i)]}. Thus, we have the following property for D.

Lemma 2.3. Let D be a random 1-regular digraph on n vertices generated according to the distribution ${\cal{C}}_{n,1}$, then a.a.s. D has at most $\log^2 n$ strongly connected components.

The next property is a key lemma of the edge distribution, which is frequently used during the proof. We use it to connect different components of the digraph. Furthermore, it is a directed version of Lemma 3.3 in Ref. [14], and their proofs are analogous. We provide a proof for completeness.

Lemma 2.4. Let $\epsilon>0$ and $k=k(n)\leqslant n^3$. For each $i\in [k]$, let $\alpha_i=\alpha_i(n)$ and $\beta_i=\beta_i(n)$ such that $\alpha_i\beta_i=\omega((\dfrac{\log n}{n})^{\tfrac{1}{2}})$, and let $U_i,V_i\subset [n]$ be two arbitrary sets of vertices with $|U_i|\geqslant\alpha_in$ and $|V_i|\geqslant\beta_in$. Let D be a random 1-regular digraph on n vertices generated according to the distribution ${\cal{C}}_{n,1}$. Then, for every $i\in [k]$, $U_i$ contains at least $(1-\epsilon)\alpha_i\beta_in$ vertices v such that $N_D^+(v)\cap V_i\not=\emptyset$.

Proof. Let P be the probability that the statement holds for D. First, we set $i\in [k]$. Let $Z=\{v\in U_i\mid N_D^+(v)\cap V_i\not=\emptyset\}$, and $X=|Z|$. Using the configuration model, for each sufficiently large $v\in U_i$ and n, we have

Hence, $E(X)\geqslant(1-\displaystyle \frac{\epsilon}{2})\alpha_i\beta_in$.

We know that X can also be viewed as a random variable in ${\cal{C}}^*_{n,1}$. Given any pair of configurations $M_1\sim M_2$, they differ in two edges at four vertices; thus, $|X(M_1)-X(M_2)|\leqslant 4$. Hence, from Lemma 2.1, we have $P(X < (1-\epsilon)\alpha_i\beta_in)\leqslant \exp\{-\varOmega (\alpha_i^2\beta_i^2n)\}.$

Finally, by the union bound, we have

3.   Proof of Theorem 1.1

It has been known that every d-regular digraph can be decomposed into the union of 1-regular digraphs^[17]. Therefore, to prove Theorem 1.1, we should only consider the case where $d=1$.

We always assume that n is sufficiently large throughout the proof. Recall that $\alpha=\omega((\dfrac{\log n}{n})^{\tfrac{1}{4}})$ and H is a digraph of n vertices with $\delta(H)\geqslant \alpha n$. Let D be a random 1-regular digraph with vertex set $V(D)=V(H)=[n]$ generated according to the distribution ${\cal{C}}_{n,1}$. For a positive number β, by applying Lemma 2.4 to the pair of sets $X,Y\in V(H)$ with $\epsilon=\dfrac{1}{2}$ and $|X|,|Y|\geqslant\beta n$, we have the following claim:

Claim. For any $X,Y\in V(H)$ (not necessarily distinct) with $|X|,|Y|\geqslant\beta n$, X contains at least $\dfrac{\beta^2n}{2}$ vertices z such that $N_D^+(z)\cap Y\not=\emptyset$.

We used the absorbing method to construct cycles of all lengths. First we select an arbitrary vertex subset $U\subset V(H)$ with $|U|$ sufficiently small when compared to n. Then, we construct a path P to ‘absorb’ vertices in U. Next, we show that there exists an almost spanning cycle C with $P\subset C$ such that C avoids U. Finally, we use C and U to determine cycles of all lengths.

For each pair of vertex subsets $(X,Y)$ (not necessarily distinct), we consider set $Z(X,Y):=\{(z,w)\in E(D)\mid z\in X,w\in Y\}$. This is the set of all ‘available’ edges for $(X,Y)$. Based on Claim 1, for all pairs of vertex subsets $(X,Y)$ with $|X|,|Y|\geqslant\beta n$ for some $\beta>0$, we have

As we consider available edges from D, the digraph $Z_{XY}=(V(H),Z(X,Y))$ has a maximum degree of 1 as follows:

Consider an arbitrary set $U\subset V(H)$ of size $m=\dfrac{\alpha^2n}{10000}$ and label it as $U=\{u_1,\cdots,u_m\}$. This is the set of vertices we want to ‘absorb’. For each $j\in [m]$, we iteratively choose an edge $e_j=(z_j,z_j^*)\in Z(N_H^-(u_j),N_H^+(u_j))$, such that $\{z_j,z_j^*\}\cap(U\cup\{z_t,z_t^*\mid t\in [j-1]\})=\emptyset$. Hence, we consider m vertex-disjoint edges in D such that they all avoid the vertex set U. We note that $\delta(H)\geqslant \alpha n$. Thus, the existence of such m edges is guaranteed by (1) and (2). Let $W=\{z_t,z_t^*\mid t\in [m]\}$. We now choose $\beta={\alpha}/5$. For each pair of vertex subsets $(X,Y)$ with $|X|,|Y|\geqslant\beta n$, we update the set of available edges by letting

By (1) and (2), we can estimate the number of available edges:

Now, for each $j\in [m-1]$, we iteratively choose $e^1_j=(w_j,w_j^*)\in Z^1(N_H^+(z^*_j),N_H^-(z_{j+1}))$ such that these edges are vertex disjoint. Similarly, (3) and (2) guarantee the existence of such edges. Therefore, we obtain a directed path $P= z_1z^*_1w_1w^*_1z_2z^*_2\cdots w_{m-1}w^*_{m-1}z_mz_m^*$ in $H\cup D$, which is used to absorb set U.

Let $W'=V(P)\setminus\{z_1,z_m^*\}$ and $D_0=(D\setminus(W'\cup U))\cup P$, i.e., $D_0$ is the union of the graph $D\setminus(W'\cup U)$ and path P. Thus, $D_0$ is a subgraph of $H\cup D$ with $\Delta(D_0)\leqslant 1$. From Lemma 2.3, $D_0$ contains at most $\log^2n$ directed cycles. Given that we removed at most $(1+o(1))\dfrac{\alpha^2 n}{2000}$ vertices from D and every vertex produces at most one directed path, $D_0$ contains at most $(1+o(1))\dfrac{\alpha^2 n}{2000}$ directed paths. We iteratively use the edges of H to combine these directed cycles and paths into a directed cycle C in $(H\cup D)\setminus U$ of length $n-m$ with $P\subset C$. Let $V=V(H)\setminus U$. For each $X,\;Y\subset V$ with $|X|,\;|Y|\geqslant\beta n$, we updated the set of available edges by setting

Using (1) and (2), we can estimate the number of available edges.

In the iteration process, for any $i\in\mathbb{N}$, we assume that we have already defined $D_{i-1}$ in the ith step. The ith step adjusts the graph by letting $D_i=(D_{i-1}\setminus E_a)\cup E_b$, where $E_a$ and $E_b$ are sets of edges of $H\cup D$ with the property that $\Delta(D_i)\leqslant 1$ for every step $i\in\mathbb{N}$. Subsequently, we update the available edges by setting $Z_i(X,Y):=Z_{i-1}(X,Y)\setminus E_a$. We assume the following in each step for each $X,Y\subset V$ with $|X|,|Y|\geqslant\beta n$.

We prove this later by showing that the number of steps performed and number of removed edges are small at each step.

For the ith step, we have graph $D_{i-1}$, and we consider the following possible cases: We refer to the component isomorphic to a directed path (resp. a direct cycle) as a path component (resp. a cycle component).

Case 1. At least two path components exist in $D_{i-1}$. We select one of them, such as $P'=v_1v_2\cdots v_\ell$, and any edge $(u,v)\in Z_{i-1}(N_H^-(v_1),N_H^+(v_\ell))$. We wet $D_i=(D_{i-1}\setminus\{(u,v)\})\cup \{(u,v_1),(v_\ell,v)\}$. If $(u,v)\in E(P')$, then recall that $P'= v_1\cdots uv\cdots v_\ell$. Therefore, $P'$ is decomposed into two directed cycles $v_1\cdots uv_1$ and $v\cdots v_\ell v$ after the operation. If $(u,v)$ belongs to another directed path component $P''$ or a directed cycle component $C'$, then $P'$ and $P''$ (or $C'$) are combined into a single directed path (or a longer directed cycle) in $D_i$. The operation deduces the number of path components by 1. The operations of Case 1 stop after we obtain $D_i$ with exactly one path component.

Case 2. There is exactly one path component in $D_{i-1}$, i.e., $P'=v_1v_2\cdots v_\ell$. We adjust the graph to extend $P'$ into a longer path while reducing the number of components if possible; otherwise, we construct a graph that is a union of vertex-disjoint cycles. We consider the following cases.

Subcase 2.1 $(v_\ell, v_1)\in E(H)$. Set $D_i=D_{i-1}\cup\{(v_\ell,v_1)\}$. This operation converts the path component $P'$ into a directed cycle.

Subcase 2.2 There exists a certain $v\in N_H^-(v_1)\setminus(U\cup V(P)\cup V(P'))$. Then, we choose vertex $v'\in N_{D_{i-1}}^+(v)$ and let $D_i= (D_{i-1}\setminus\{(v,v')\})\cup\{(v,v_1)\}$. This operation extends $P'$ into a longer directed path in $D_i$ ($P'$ and the cycle containing $(v, v')$ is adjusted to a longer directed path) and reduces the number of components by one. We can do similar operation if there exists some $v\in N_H^+(v_\ell)\setminus(U\cup V(P)\cup V(P'))$.

Subcase 2.3. $(N_H^-(v_1)\cup N_H^+(v_\ell))\setminus(U\cup V(P))\subseteq V(P')$. We first introduce some notations used here. For $v_i\in V(P')$, let $v_i^+=v_{i+1}$ for $i\in[\ell-1]$ and $v_i^-=v_{i-1}$ for $i\in[2,\ell]$. With respect to $U\subset V(P')$, let $U^+=\{v^+\mid v\in U\}$ and $U^-=\{v^-\mid v\in U\}$. Given two vertex subsets $U,V\subset V(P')$, let $U^*=\{i\in [\ell]\mid v_i\in U\}$ and $V^*=\{i\in [\ell]\mid v_i\in V\}$. We can state that $U<V$ if $\max U^*< \min V^*$. It should be noted that $\delta(H)\geqslant 5\beta n$ and $|U\cup V(P)|\leqslant 5m < \beta n$. We can partition $N_H^-(v_1)\cap V(P')$ into $U_1$ and $U_2$ such that $U_1<U_2$ with $|U_1|\geqslant 3\beta n$ and $|U_2|\geqslant \beta n$. Similarly, we can partition $N_H^+(v_\ell)\cap V(P')$ into $W_1$ and $W_2$ such that $W_1<W_2$ with $|W_1|\geqslant \beta n$ and $|W_2|\geqslant 3\beta n$.

If $W_1<U_2$, then $|W_1^-|, |U_2^+|\geqslant \beta n$. Based on (5), there is an edge $(w_1^-, u_2^+)\in Z_{i-1}(W_1^-, U_2^+)$. We wet $D_i=(D_{i-1}\setminus\{(w_1^-,w_1), (u_2,u_2^+)\})\cup\{(w_1^-, u_2^+), (u_2,v_1),(v_\ell,w_1)\}$. This operation converts $P'$ into a directed cycle.

Otherwise, we have $\max U_1^*<\min U_2^*<\max W_1^*<\min W_2^*$, i.e., $U_1<W_2$. Let $U_{12}$ be the last $\beta n$ vertices of $U_1$, i.e., $(U_1\setminus U_{12})<U_{12}$. Clearly, $|U_1\setminus U_{12}|\geqslant 2\beta n$. Let $U_{11}=\{v\in U_1\setminus U_{12}\mid N_D^+(v)\cap U_{12}^+\not=\emptyset\}$; It is claimed that $|U_{11}|\geqslant \beta n$. If this is not true, then $|U_1\setminus (U_{12}\cup U_{11})|\geqslant \beta n$. Given that $|U_{12}^+|=\beta n$, Claim 1 guarantees that at least $\dfrac{\beta^2n}2$ edges are available from $U_1\setminus (U_{12}\cup U_{11})$ to $U_{12}^+$. However, this contradicts the definition of $U_{11}$. Thus, $|U_{11}|\geqslant\beta n$. Similarly, let $W_{21}$ be the first $\beta n$ vertices of $W_2$, and let $W_{22}=\{v\in W_2\setminus W_{21} \mid N_D^-(v)\cap W_{21}^-\not=\emptyset\}$. Hence, we can state $|W_{22}|\geqslant\beta n$. Based on (5), there exists an edge $(w_{22}^-, u_{11}^+)\in Z_{i-1}(W_{22}^-,U_{11}^+)$. Additionally, by definition, $u _{12}\in\,U _{12}$ and $w _{21}\in\,W _{21}$ exist such that $(u_{11},u_{12}^+),\;(w_{21}^-,w_{22})\in E(D)$. Set

and $D_i=(D_{i-1}\setminus E_a)\cup E_b.$ This operation turns the path component $P'$ into a directed cycle.

Case 3. All the components of $D_{i-1}$ are directed cycles. If $D_{i-1}$ is a single directed cycle, then our proof is completed. Now, we assume that $D_{i-1}$ contains at least two components. In this iteration process, we reduce the number of components by one while creating a path. Let $C'$ be the longest directed cycle in $D_{i-1}$.

If $|V(C')|\geqslant n-\alpha n$ or $|V(C')|<\alpha n$, then the other cycle components exhibit lengths that are less than $\alpha n$. Given that $\delta(H)\geqslant\alpha n$, there must be an edge $e'=(u,v)\in E(H)$ joining $C'$ and some other cycle component $C''$ in both cases. Now assume $\alpha n\leqslant |V(C')| < n-\alpha n$. Based on (5), there exists an available edge $e'=(u,v)\in Z_i(V(C'), [n]\setminus V(C'))$, i.e., $e'$ joins $C'$ and some other cycle component $C''$. Suppose that $(u,u')\in E(C')$, and $(v',v)\in E(C')$. Set $D_i=(D_{i-1}\setminus\{(u,u'), (v',v)\})\cup \{(u,v)\}$. This operation converts $C'$ and $C''$ into a directed path and reduces the number of components by one.

First, we claim that the aforementioned process stops after finite steps. The operations in Case 1 are iterated $t-1$ times, where $t\leqslant (1+o(1))\dfrac{\alpha^2n}{2000}$ is the number of path components in $D_0$. This is due to the fact that after the process of Case 1, the number of path components of $D_i$ will never be more than one again. Next, if we perform the operation of Subcases 2.1 or 2.3, the next process must be Case 3, and each iteration of Case 3 decrease the number of components by one; otherwise, Subcase 2.2 is performed, and the number of components will also be reduced by one. Therefore, after finite iterations (at most $4 (t-1) +2 \log^2n$), we obtain a graph $D_i$ with only one cycle component C. Given that we do not destroy path P in each iteration, we have $P\subset C$. Thus, the total number of iterations is at most $N\leqslant 5t+2\log^2n\leqslant (1+o(1))\dfrac{\alpha^2n}{400}$, and in each iteration, we remove at most 4 edges such that at most $(1+o(1))\dfrac{\alpha^2n}{100}=(1+o(1))\dfrac{\beta^2n}{4}$ edges are removed, which implies (5).

Remark 3.1. Specifically, for any subset $U'$ of size at most m, we can use the above process to construct an almost Hamiltonian cycle in $H\cup D$ which misses $U'$.

We now use the directed cycle C constructed above to construct directed cycles $C_k$ of all possible lengths $k\in[3,n]$. It should be noted that C has a length of $n-m$. We consider the following cases.

Case 1. $n-m\leqslant k\leqslant n$. We use $P\subset C$ to absorb some vertices of U to obtain a directed cycle of the desired length. We choose an arbitrary subset $I\subset [m]$ with $|I|=k+m-n$. For each $i\in I$, replace the edge $(z_i,z_i^*)$ with the directed path $z_iu_iz_i^*$, and the resulting directed cycle has length k as desired.

Case 2. $3\leqslant k<n-m$. Fix a vertex u. It should be noted that $\delta(H)\geqslant \alpha n$, and there must be an available edge $(v, w)\in Z(N_H^+(u), N_H^-(u))$. Thus, $uvwu$ is a directed cycle of length 3 in $H\cup D$. Now, we assume that $4\leqslant k<n-m$. We choose $U^-\subset N_H^-(u)$ and $U^+\subset N_H^+(u)$ with $|U^-|=|U^+|=\dfrac{m}{4}= \dfrac{\alpha^2 n}{40000}$. From Lemma 2.4, an available edge $(v, w) \in Z (U ^ +, U ^-)$ must exist. Let $W^-=\{v\in V\mid N_D^+(v)\cap U^-=\emptyset\}$ and $W^+=\{v\in V\mid N_D^- (v)\cap U^+=\emptyset\}$. From Lemma 2.4, the size of $W^-$ and $W^+$ must be $o(n)$. Therefore, we assume that $|W^-|,\;|W^+| < \dfrac{m}{4}$. Let $U'= \{u\}\cup U^-\cup U^+\cup W^-\cup W^+$. Then, $|U'|<m$. As stated in Remark A, we can construct a directed cycle $C'$ of length $n-m$ in $H\cup D$, missing $U'$. Therefore, we can select a directed path $P'=y_1y_2\cdots y_{k-3}$ of length $k-4$. According to the definitions of $W^-$ and $W^+$, $a \in U ^ -$ and $b \in U ^ +$ must exist such that $(y_{k-3},a),\;(b,y_1)\in E(H)$. Thus, $P'\cup y_{k-3}auby_1$ is a directed cycle of desired length.

This completes the proof of Theorem 1.1.

Remark 3.2. As this proof is constructive, by retracing the proof, one can find cycles of any given length in $H\cup D$ in gradual steps. Given that each step can be performed in polynomial time (at most $O(n^3)$ times) and there are $O (\alpha n)$ steps at most, the proof provides a polynomial-time algorithm.

4.   Concluding remarks and discussions

In this study, we show that for a given digraph H on n vertices with a minimum degree of at least $\alpha n$ (where $\alpha=\omega\left( {\left( {\dfrac{\log n}{n}} \right)^{\tfrac{1}{4}}} \right)$), we can a.a.s. obtain a pancyclic digraph by perturbing it with a random d-regular digraph when $d=1$ or 2. However, there is no evidence that the lower bound of the minimum degree of H is tight, and we believe that the bound is far from optimal. It would be interesting to obtain an optimal lower bound of $\delta(H)$.

A natural question is to extend the pancyclicity to vertex-pancyclicity, i.e., for any $v\in V(H)$ and $k\in [3,n]$, there exists a directed cycle C of length k passing v, and we leave this as an open problem.

Problem 4.1. Let $\alpha=\omega\left( {\left( {\dfrac{\log n}{n}} \right)^{\tfrac{1}{4}}} \right)$ and $d\in\{1,2\}$ and let H be a graph of n vertices with $\delta(H)\geqslant4\alpha n$. Then, a.a.s. $H\cup D$ is vertex-pancyclic, where D is a random d-regular digraph on n vertices.

Acknowledgements

This work was supported by National Natural Science Foundation of China (12071453) and the National Key R&D Program of China (2020YFA0713100).

Conflict of interest

The authors declare that they have no conflict of interest.