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 \(\delta^0(W)=\mbox{min}\{\delta^+(W),\delta^-(W)\}\), where \(\delta^+(W)\) is the minimum out-degree of \(W\) in \(D\) and \(\delta^-(W)\) is the minimum in-degree of \(W\) in \(D\). Let \(k\) be an integer with \(k\geq 1\). In this paper, we prove that for any positive integer partition \(|W|=\sum_{i=1}^{k}n_i\) with \(n_i\geq 2\) for each \(i\), if \(\delta^0(W)\geq \frac{3n-3}{4}\), then there are \(k\) vertex disjoint cycles \(C_1,\ldots,C_k\) in \(D\) such that each \(C_i\) contains exactly \(n_i\) vertices of \(W\). Moreover, the lower bound of \(\delta^0(W)\) can be improved to \(\frac{n}{2}\) if \(k=1\), and \(\frac{n}{2}+|W|-1\) if \(n\geq 2|W|\). The minimum semi-degree condition \(\delta^0(W)\geq \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].