Linear k-Arboricity in Product Networks

摘要

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 la_k(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{la_k(G),la_ℓ(H)} ≤ la_(max{k,ℓ})(G□H) ≤ la_k(G)+ la_ℓ(H) for any two graphs G and H. Denote by G ○ H, G × H and G(⊠)H the lexicographic product, direct product and strong product of two graphs G and H, respectively. For any two graphs G and H, we also derive upper and lower bounds of la_k(G ○ H), la_k(G × H) and la_k(G(⊠)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 hyper Petersen network are also studied.