The linear $ k $-arboricity of symmetric directed trees

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

doi:10.3934/math.2022093

AIMS Mathematics

2022, Volume 7, Issue 2: 1603-1614. doi: 10.3934/math.2022093

Previous Article Next Article

Research article

The linear $ k $-arboricity of symmetric directed trees

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 510006, China

Received: 29 May 2021 Accepted: 26 October 2021 Published: 29 October 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 arc-disjoint linear $ k $-diforests whose union covers all the arcs of $ D $. In this paper, we study the linear $ k $-arboricity for symmetric directed trees and fully determine the linear $ 2 $-arboricity for all symmetric directed trees.
- linear $ k $-arboricity,
- digraphs,
- directed trees,
- symmetric directed trees,
- linear arboricity
Citation: Xiaoling Zhou, Chao Yang, Weihua He. The linear $ k $-arboricity of symmetric directed trees[J]. AIMS Mathematics, 2022, 7(2): 1603-1614. doi: 10.3934/math.2022093

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 arc-disjoint linear $ k $-diforests whose union covers all the arcs of $ D $. In this paper, we study the linear $ k $-arboricity for symmetric directed trees and fully determine the linear $ 2 $-arboricity for all symmetric directed trees.

References

[1]	J. Akiyama, G. Exoo, F. Harary, Covering and packing in graphs, III: Cyclic and acyclic invariants, Math. Slovaca, 30 (1980), 405–417.
[2]	N. Alon, Probabilistic methods in coloring and decomposition problems, Discerte Math., 127 (1994), 31–46. doi: 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, Graphs Combinatorics, 17 (2001), 11–16. doi: 10.1007/PL00007233. doi: 10.1007/PL00007233
[4]	B. Alspach, J. C. Bermond, D. Sotteau, Decomposition into Cycles I: Hamilton decompositions, 3 Eds., Netherlands: Springer, 1990. doi: 10.1007/978-94-009-0517-7_2.
[5]	R. D. Baker, R. M. Wilson, Nearly Kirkman triple systems, Utilitas Math., 11 (1977), 289–296.
[6]	J. C. Bermond, J. Fouquet, M. Habib, B. Péroche, On linear $k$-arboricity, Discrete Math., 52 (1984), 123–132. doi: 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. doi: 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. doi: 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. doi: 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, Ser. B, 142 (2020), 56–79. doi: 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 Comb., 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. doi: 10.1016/j.disc.2007.07.067. doi: 10.1016/j.disc.2007.07.067
[13]	M. Habib, B. Péroche, Some problems about linear arboricity, Discrete Math., 41 (1982), 219–220. doi: 10.1016/0012-365X(82)90209-6. doi: 10.1016/0012-365X(82)90209-6
[14]	F. Harary, Coverings and packing in graphs, I, Ann. New York Academy Sci., 175 (1970), 198–205. doi: 10.1111/j.1749-6632.1970.tb45132.x. doi: 10.1111/j.1749-6632.1970.tb45132.x
[15]	W. He, H. Li, Y. Bai, Q. Sun, Linear arboricity of regular digraphs, Acta Math. Sin., Engl. Ser., 33 (2017), 501–508. doi: 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. doi: 10.1016/0012-365X(95)00293-6. doi: 10.1016/0012-365X(95)00293-6
[17]	A. Nakayama, B. Péroche, Linear arboricity of digraphs, Networks, 17 (1987), 39–53. doi: 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. doi: 10.1090/pspum/019/9959. doi: 10.1090/pspum/019/9959
[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, Ser. B, 75 (1999), 100–109. doi: 10.1006/jctb.1998.1868. doi: 10.1006/jctb.1998.1868
[20]	J. L. Wu, On the linear arboricity of planar graphs, J. Graph Theory, 31 (1999), 129–134. doi: 10.1002/(SICI)1097-0118(199906)31:21.0.CO; 2-3. doi: 10.1002/(SICI)1097-0118(199906)31:21.0.CO;2-3
[21]	B. Xue, L. Zuo, On the linear $(n-1)$-arboricity of $K_{n(m)}$, Discrete Appl. Math., 158 (2010), 1546–1550. doi: 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. doi: 10.11650/twjm/1500405741. doi: 10.11650/twjm/1500405741
[23]	X. Zhou, C. Yang, W. He, The linear $k$-arboricity of digraphs, unpublished work.

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)