1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

A Decomposition for Digraphs with Minimum Outdegree 3 Having No Vertex Disjoint Cycles of Different Lengths

Published Online: 21 Jan 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 19 Jun 2020
Accepted: 17 Nov 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

We say that a digraph D = (V, A) admits a good decomposition D = D1D2D3 if D1 = (V1, A1), D2 = (V2, A2) and D3 = (V3, A3) are such subdigraphs of D that V = V1V2 with V1V2 = ∅, V2 ≠ ∅ but V1 may be empty, D1 is the subdigraph of D induced by V1 and is an acyclic digraph, D2 is the subdigraph of D induced by V2 and is a strong digraph and D3 is a subdigraph of D, every arc of which has its tail in V1 and its head in V2. 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 = D1D2D3, where D1 = (V1, A1), D2 = (V2, A2) and D3 = (V3, A3) are such that D2 has minimum outdegree 3 and no vertex disjoint directed cycles of different lengths and for every vertex vV1, d+D1∪D3(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

MSC 2010

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

[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. doi:10.37236/692110.37236/6921Search in Google Scholar

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

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

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

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

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

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

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

[10] C. Thomassen, Disjoint cycles in digraphs, Combinatorica 3 (1983) 393–396. doi:10.1007/BF0257919510.1007/BF02579195Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo