2016/03/14 by Yaping Mao, Zhiwei Guo, Mao, Yaping +5
Business, Management and Accounting · Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Product Development and Customization #math.CO
paper · pdf · doi:10.48550/arxiv.1603.04121
27 pages
arxiv created 2016/03/14 · openalex publication_date 2016/03/14 · arxiv updated 2016/03/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A linear k-forest is a forest whose components are paths of length at most k. The linear k-arboricity of a graph G, denoted by \rm lak(G), is the least number of linear k-forests needed to decompose G. Recently, Zuo, He and Xue studied the exact values of the linear (n-1)-arboricity of Cartesian products of various combinations of complete graphs, cycles, complete multipartite graphs. In this paper, for general k we show that max\\rm lak(G),\rm laℓ(H)\≤ \rm la_max\k,ℓ\(G\Box H)≤ \rm lak(G)+\rm laℓ(H) for any two graphs G and H. Denote by G∘ H, G× H and G\boxtimes H the lexicographic product, direct product and strong product of two graphs G and H, respectively. We also derive upper and lower bounds of \rm lak(G∘ H), \rm lak(G× H) and \rm lak(G\boxtimes H) in this paper. The linear k-arboricity of a 2-dimensional grid graph, a r-dimensional mesh, a r-dimensional torus, a r-dimensional generalized hypercube and a 2-dimensional hyper Petersen network are also studied.