Disjoint Cycles in a Digraph with Partial Degree
Hong Wang, Yun Wang, Yan Jin · SIAM Journal on Discrete Mathematics · 2023
Abstract. Let [Formula: see text] be a digraph of order [Formula: see text]. We define the degree of vertex [Formula: see text] in [Formula: see text] to be [Formula: see text], where [Formula: see text] and [Formula: see text] are the out-degree and in-degree of [Formula: see text] in [Formula: see text], respectively. Let [Formula: see text] be a positive integer and let [Formula: see text] be any given subset of [Formula: see text] with [Formula: see text]. In this paper we show that if [Formula: see text] for all [Formula: see text], then for any integer partition [Formula: see text] with [Formula: see text] for each [Formula: see text], there are [Formula: see text] disjoint cycles containing exactly [Formula: see text] vertices of [Formula: see text], respectively. The degree condition [Formula: see text] is sharp in some sense and this result confirms the conjecture posed by Wang [J. Graph Theory, 34 (2000), pp. 154–162] as a corollary. The result in this paper implies a theorem on cycle-factors containing matchings in bipartite graphs. Further, the special case [Formula: see text] is a directed version of the Aigner–Brandt theorem on disjoint cycles in graphs.