Article in volume
Authors:
Title:
A decomposition for digraphs with minimum outdegree 3 having no vertex disjoint cycles of different lengths
PDFSource:
Discussiones Mathematicae Graph Theory 43(2) (2023) 573-581
Received: 2020-06-19 , Revised: 2020-11-17 , Accepted: 2020-11-17 , Available online: 2020-12-07 , https://doi.org/10.7151/dmgt.2381
Abstract:
We say that a digraph $D=(V,A)$ admits a good decomposition $D=D_1\cup D_2\cup
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\cup V_2$ with $V_1\cap V_2=\emptyset$, $V_2\ne\emptyset$ 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\cup D_2\cup 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\in V_1$, $d^+_{D_1\cup D_3}(v)\ge 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
References:
- J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications (Springer, London, 2001).
https://doi.org/10.1007/978-1-4471-3886-0 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - N.D. Tan, On $3$-regular digraphs of girth $4$, Discrete Math. 343 (2020) 111632.
https://doi.org/10.1016/j.disc.2019.111632 - C. Thomassen, Disjoint cycles in digraphs, Combinatorica 3 (1983) 393–396.
https://doi.org/10.1007/BF02579195
Close