On directed version of the Sauer-Spender Theorem

Abstract

Let $D=(V,A)$ be a digraph of order $n$ and let $W$ be any subset of $V$. We define the minimum semi-degree of $W$ in $D$ to be $δ^0(W)=\mbox{min}\{δ^+(W),δ^-(W)\}$, where $\hat{I}{´}^{+}(W)$ is the minimum out-degree of $W$ in $D$ and $\hat{I}{´}^{-}(W)$ is the minimum in-degree of $W$ in $D$. Let $k$ be an integer with $k\ge 1$. In this paper, we prove that for any positive integer partition $|W|={\sum }_{i=1}^k{n}_i$ with $n_i\ge 2$ for each $i$, if $\hat{I}{´}^0(W)\ge \frac{3n-3}{4}$, then there are $k$ vertex disjoint cycles $C_1,\dots ,C_k$ in $D$ such that each $C_i$ contains exactly $n_i$ vertices of $W$. Moreover, the lower bound of $\hat{I}{´}^0(W)$ can be improved to $\frac{n}{2}$ if $k=1$, and $\frac{n}{2}+|W|-1$ if $n\ge 2|W|$. The minimum semi-degree condition $\hat{I}{´}^0(W)\ge \frac{3n-3}{4}$ is sharp in some sense and this result partially confirms the conjecture posed by Wang [Graphs and Combinatorics 16 (2000) 453-462]. It is also a directed version of the Sauer-Spender Theorem on vertex disjoint cycles in graphs [J. Combin. Theory B, 25 (1978) 295-302].

18 pages and 3 figures