On directed 2-factors in digraphs and 2-factors containing perfect matchings in bipartite graphs

Abstract

In this paper, we give the following result: If $D$ is a digraph of order $n$, and if $d_D^{+}(u)+d_D^{-}(v)\ge n$ for every two distinct vertices $u$ and $v$ with $(u,v)\notin A(D)$, then $D$ has a directed $2$-factor with exactly $k$ directed cycles of length at least $3$, where $n\ge 12k+3$. This result is equivalent to the following result: If $G$ is a balanced bipartite graph of order $2n$ with partite sets $X$ and $Y$, and if $d_G(x)+d_G(y)\ge n+2$ for every two vertices $x\in X$ and $y\in Y$ with $xy\notin E(G)$, then for every perfect matching $M$, $G$ has a $2$-factor with exactly $k$ cycles of length at least $6$ containing every edge of $M$, where $n\ge 12k+3$. These results are generalizations of theorems concerning Hamilton cycles due to Woodall (1972) and Las Vergnas (1972), respectively.

19 pages, 10 figures