Partitioning the vertices of a digraph into directed cycles and degenerated directed cycles.

In this paper, we prove the following result: If D is a digraph of order n ≥ k , and if d D + (u) + d D − (v) ≥ n − k + 1 for every two distinct vertices u and v with (u , v) ∉ A (D) , then one of the following (i) and (ii) holds: (i) D contains k vertex-disjoint subdigraphs H 1 , ... , H k such that ⋃ 1 ≤ i ≤ k V (H i) = V (D) and for all i , 1 ≤ i ≤ k , H i is a directed cycle of order at least 3 or a directed path of order at most 2; (ii) k = 2 and D is the digraph obtained from a cycle of order 5 by replacing each of its edges by two oppositely oriented arcs with the same ends. In the connected case, we further show the existence of such k vertex-disjoint subdigraphs as (i) in which the number of directed cycles is bounded above by 2 (if the exceptional case (ii) does not occur). This is a common generalization of the results obtained by Woodall (1972) and, Enomoto and Li (2004), respectively. [ABSTRACT FROM AUTHOR]