Partition of a directed bipartite graph into two directed cycles (Q1126308)

The main result is the following theorem: Let \(D=(V_1,V_2; A)\) be a directed bipartite graph with \(|V_1|=|V_2|= n\geq 2\). Suppose that \(d_D(x)+ d_D(y)\geq 3n+1\) for all \(x\in V_1\) and \(y\in V_2\). (\(d_D(x)\) denotes the number of vertices which are joined with the vertex \(x\) with an arc outgoing from \(x\) or incoming in \(x\).) Then \(D\) contains two vertex-disjoint directed cycles of lengths \(2n_1\) and \(2n_2\) respectively, for any positive integer partition \(n= n_1+n_2\). A bipartite graph which shows that the condition is sharp for even \(n\) and nearly sharp for odd \(n\) is constructed. The authors use several lemmas. Two of them were proved by \textit{J. A. Bondy} and \textit{V. Chvátal} [Discrete Math. 15, 111-135 (1976; Zbl 0331.05138)]. The second of these lemmas reads: If \(d_G(x)+ d_G(y)\geq n+1\) for any two non-adjacent vertices \(x\in V_1\) and \(y\in V_2\) of a nonoriented bipartite graph \(G=(V_1,V_2)\), then \(G\) is Hamiltonian.