The linear $ k $-arboricity of digraphs

Xiaoling Zhou; Chao Yang; Weihua He; Xiaoling Zhou; Chao Yang; Weihua He

doi:10.3934/math.2022229

AIMS Mathematics

2022, Volume 7, Issue 3: 4137-4152. doi: 10.3934/math.2022229

Previous Article Next Article

Research article

The linear $ k $-arboricity of digraphs

1.
School of Mathematics and Statistics, Guangdong University of Technology, Guangzhou 510520, China
2.
School of Mathematics and Statistics, Guangdong University of Foreign Studies, Guangzhou 510520, China

Received: 02 July 2021 Revised: 25 November 2021 Accepted: 10 December 2021 Published: 15 December 2021
MSC : 05C70, 05C38

A linear $ k $-diforest is a directed forest in which every connected component is a directed path of length at most $ k $. The linear $ k $-arboricity of a digraph $ D $ is the minimum number of linear $ k $-diforests needed to partition the arcs of $ D $. In this paper, we study the linear $ k $-arboricity for digraphs, and determine the linear $ 3 $-arboricity and linear $ 2 $-arboricity for symmetric complete digraphs and symmetric complete bipartite digraphs.
- linear $ k $-arboricity,
- digraphs,
- symmetric complete digraphs,
- symmetric complete bipartite digraphs
Citation: Xiaoling Zhou, Chao Yang, Weihua He. The linear $ k $-arboricity of digraphs[J]. AIMS Mathematics, 2022, 7(3): 4137-4152. doi: 10.3934/math.2022229

Related Papers:

Abstract

A linear $ k $-diforest is a directed forest in which every connected component is a directed path of length at most $ k $. The linear $ k $-arboricity of a digraph $ D $ is the minimum number of linear $ k $-diforests needed to partition the arcs of $ D $. In this paper, we study the linear $ k $-arboricity for digraphs, and determine the linear $ 3 $-arboricity and linear $ 2 $-arboricity for symmetric complete digraphs and symmetric complete bipartite digraphs.

References

[1]	J. Akiyama, G. Exoo, F. Harary, Covering and packing in graphs Ⅲ: Cyclic and acyclic invariants, Math. Slovaca, 30 (1980), 405–417.
[2]	N. Alon, Probabilistic methods in coloring and decomposition problems, Discrete Math., 127 (1994), 31–46. https://doi.org/10.1016/0012-365X(92)00465-4 doi: 10.1016/0012-365X(92)00465-4
[3]	N. Alon, V. J. Teague, N. C. Wormald, Linear arboricity and linear k-arboricity of regular graphs, Graph. Combinator., 17 (2001), 11–16. https://doi.org/10.1007/PL00007233 doi: 10.1007/PL00007233
[4]	B. Alspach, J. C. Bermond, D. Sotteau, Decomposition into cycles I: Hamilton decompositions, In: G. Hahn, G. Sabidussi, R. E. Woodrow, Cycles and rays, Dordrecht: Springer, 1990, 9–18. https://doi.org/10.1007/978-94-009-0517-7
[5]	R. D. Baker, R. M. Wilson, Nearly Kirkman triple systems, Utilitas Math., 11 (1977), 289–296.
[6]	J. C. Bermond, J. L. Fouquet, M. Habib, B. Peroche, On linear $k$-arboricity, Discrete Math., 52 (1984), 123–132. https://doi.org/10.1016/0012-365X(84)90075-X doi: 10.1016/0012-365X(84)90075-X
[7]	G. J. Chang, Algorithmic aspects of linear $k$-arboricity, Taiwanese J. Math., 3 (1999), 71–81. https://doi.org/10.11650/twjm/1500407055 doi: 10.11650/twjm/1500407055
[8]	G. J. Chang, B. L. Chen, H. L. Fu, K. C. Huang, Linear $k$-arboricities on trees, Discrete Appl. Math., 103 (2000), 281–287. https://doi.org/10.1016/S0166-218X(99)00247-4 doi: 10.1016/S0166-218X(99)00247-4
[9]	B. L. Chen, K. C. Huang, On the linear $k$-arboricity of $K_n$ and $K_{n, n}$, Discrete Math., 254 (2002), 51–61. https://doi.org/10.1016/S0012-365X(01)00365-X doi: 10.1016/S0012-365X(01)00365-X
[10]	A. Ferber, J. Fox, V. Jain, Towards the linear arboricity conjecture, J. Comb. Theory B, 142 (2020), 56–79. https://doi.org/10.1016/j.jctb.2019.08.009 doi: 10.1016/j.jctb.2019.08.009
[11]	H. L. Fu, K. C. Huang, The linear $2$-arboricity of complete bipartite graphs, Ars Combin., 38 (1994), 309–318.
[12]	H. L. Fu, K. C. Huang, C. H. Yen, The linear $3$-arboricity of $K_{n, n}$ and $K_{n}$, Discrete Math., 308 (2008), 3816–3823. https://doi.org/10.1016/j.disc.2007.07.067 doi: 10.1016/j.disc.2007.07.067
[13]	M. Habib, B. Peroche, Some problems about linear arboricity, Discrete Math., 41 (1982), 219–220. https://doi.org/10.1016/0012-365X(82)90209-6 doi: 10.1016/0012-365X(82)90209-6
[14]	F. Harary, Coverings and packing in graphs, Ⅰ, Ann. New York Acad. Sci., 175 (1970), 198–205. https://doi.org/10.1111/j.1749-6632.1970.tb56470.x doi: 10.1111/j.1749-6632.1970.tb56470.x
[15]	W. H. He, H. Li, Y. D. Bai, Q. Sun, Linear arboricity of regular digraphs, Acta Math. Sin. (Engl. Ser.), 33 (2017), 501–508. https://doi.org/10.1007/s10114-016-5071-9 doi: 10.1007/s10114-016-5071-9
[16]	B. Jackson, N. C. Wormald, On the linear $k$-arboricity of cubic graphs, Discrete Math., 162 (1996), 293–297. https://doi.org/10.1016/0012-365X(95)00293-6 doi: 10.1016/0012-365X(95)00293-6
[17]	A. Nakayama, B. Peroche, Linear arboricity of digraphs, Networks, 17 (1987), 39–53. https://doi.org/10.1002/net.3230170104 doi: 10.1002/net.3230170104
[18]	D. K. Ray-Chauduri, R. M. Wilson, Solution of Kirkman's schoolgirl problem, Proc. Symp. Pure Math., 19 (1971), 187–203.
[19]	C. Thomassen, Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5, J. Comb. Theory B, 75 (1999), 100–109. https://doi.org/10.1006/jctb.1998.1868 doi: 10.1006/jctb.1998.1868
[20]	J. L. Wu, On the linear arboricity of planar graphs, J. Graph Theor., 31 (1999), 129–134. https://doi.org/10.1002/(SICI)1097-0118(199906)31:2<129::AID-JGT5>3.0.CO;2-A doi: 10.1002/(SICI)1097-0118(199906)31:2<129::AID-JGT5>3.0.CO;2-A
[21]	B. Xue, L. C. Zuo, On the linear ($n-1$)-arboricity of ${K_{n}}_{(m)}$, Discrete Appl. Math., 158 (2010), 1546–1550. https://doi.org/10.1016/j.dam.2010.04.013 doi: 10.1016/j.dam.2010.04.013
[22]	C. H. Yen, H. L. Fu, Linear $2$-arboricity of the complete graph, Taiwanese J. Math., 14 (2010), 273–286. https://doi.org/10.11650/twjm/1500405741 doi: 10.11650/twjm/1500405741

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)