A decomposition for digraphs with minimum outdegree 3 having no vertex disjoint cycles of different lengths

Tan, Ngo Dac 

Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 573-581

Résumé

We say that a digraph D=(V,A) admits a good decomposition D=D_1∪ D_2∪ D_3 if D_1=(V_1,A_1), D_2=(V_2,A_2) and D_3=(V_3,A_3) are such subdigraphs of D that V=V_1∪ V_2 with V_1∩ V_2=∅, V_2∅ but V_1 may be empty, D_1 is the subdigraph of D induced by V_1 and is an acyclic digraph, D_2 is the subdigraph of D induced by V_2 and is a strong digraph and D_3 is a subdigraph of D, every arc of which has its tail in V_1 and its head in V_2. In this paper, we show that a digraph D=(V,A) with minimum outdegree 3 has no vertex disjoint directed cycles of different lengths if and only if D admits a good decomposition D=D_1∪ D_2∪ D_3, where D_1=(V_1,A_1), D_2=(V_2,A_2) and D_3=(V_3,A_3) are such that D_2 has minimum outdegree 3 and no vertex disjoint directed cycles of different lengths and for every vertex v∈ V_1, d_D_1∪ D_3^+ (v)≥ 3. Moreover, when such a good decomposition for D exists, it is unique. By these results, the investigation of digraphs with minimum outdegree 3 having no vertex disjoint directed cycles of different lengths can be reduced to the investigation of strong such digraphs. Further, we classify strong digraphs with minimum outdegree 3 and girth 2 having no vertex disjoint directed cycles of different lengths.

Détail

Keywords: digraph with minimum outdegree 3, vertex disjoint cycles, cycles of different lengths, acyclic digraph, strong digraph