Geodesic
A decomposition for digraphs with minimum outdegree 3 having no vertex disjoint cycles of different lengths
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 573-581 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: digraph with minimum outdegree 3, vertex disjoint cycles, cycles of different lengths, acyclic digraph, strong digraph 
@article{DMGT_2023_43_2_a16,
     author = {Tan, Ngo Dac},
     title = {A decomposition for digraphs with minimum outdegree 3 having no vertex disjoint cycles of different lengths},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {573--581},
     year = {2023},
     volume = {43},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a16/}
}
TY  - JOUR
AU  - Tan, Ngo Dac
TI  - A decomposition for digraphs with minimum outdegree 3 having no vertex disjoint cycles of different lengths
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 573
EP  - 581
VL  - 43
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a16/
LA  - en
ID  - DMGT_2023_43_2_a16
ER  - 
%0 Journal Article
%A Tan, Ngo Dac
%T A decomposition for digraphs with minimum outdegree 3 having no vertex disjoint cycles of different lengths
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 573-581
%V 43
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a16/
%G en
%F DMGT_2023_43_2_a16
Tan, Ngo Dac. A decomposition for digraphs with minimum outdegree 3 having no vertex disjoint cycles of different lengths. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 573-581. http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a16/

[1] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications (Springer, London, 2001). https://doi.org/10.1007/978-1-4471-3886-0

[2] J. Bensmail, A. Harutyunyan, N.K. Le, B. Li and N. Lichiardopol, Disjoint cycles of different lengths in graphs and digraphs, Electron. J. Combin. 24(4) (2017) #P4.37. https://doi.org/10.37236/6921

[3] Y. Gao and D. Ma, Disjoint cycles with different length in 4-arc-dominated digraphs, Oper. Res. Lett. 41 (2013) 650–653. https://doi.org/10.1016/j.orl.2013.09.003

[4] M.A. Henning and A. Yeo, Vertex disjoint cycles of different length in digraphs, SIAM J. Discrete Math. 26 (2012) 687–694. https://doi.org/10.1137/100802463

[5] N. Lichiardopol, Proof of a conjecture of Henning and Yeo on vertex-disjoint directed cycles, SIAM J. Discrete Math. 28 (2014) 1618–1627. https://doi.org/10.1137/130922653

[6] N.D. Tan, Vertex disjoint cycles of different lengths in d-arc-dominated digraphs, Oper. Res. Lett. 42 (2014) 351–354. https://doi.org/10.1016/j.orl.2014.06.004

[7] N.D. Tan, On vertex disjoint cycles of different lengths in 3-regular digraphs, Discrete Math. 338 (2015) 2485–2491. https://doi.org/10.1016/j.disc.2015.06.016

[8] N.D. Tan, On 3-regular digraphs without vertex disjoint cycles of different lengths, Discrete Math. 340 (2017) 1933–1943. https://doi.org/10.1016/j.disc.2017.03.024

[9] N.D. Tan, On 3-regular digraphs of girth 4, Discrete Math. 343 (2020) 111632. https://doi.org/10.1016/j.disc.2019.111632

[10] C. Thomassen, Disjoint cycles in digraphs, Combinatorica 3 (1983) 393–396. https://doi.org/10.1007/BF02579195