Directed Bipartite Graphs Containing Every Possible Pair of Directed Cycles

Abstract

Let $D=(V_1,V_2;A)$ be a directed bipartite graph with $|V_1|=|V_2|=n\ge 2$. Suppose that $d_D(x)+d_D(y)\ge 3n$ for all $x\in V_1$ and $y\in V_2$. Then, with one exception, $D$ contains two vertex-disjoint directed cycles of lengths $2s$ and $2t$, respectively, for any two positive integers $s$ and $t$ with $s+t\le n$.