Line k-Arboricity in Product Networks

A \emph{linear $k$-forest} is a forest whose components are paths of length at most $k$. The \emph{linear $k$-arboricity} of a graph $G$, denoted by ${\rm la}k(G)$,istheleastnumberoflinear$k$-forestsneededtodecompose$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 la}{k}(G),{\rm la}{\ell}(H)}\leq {\rm la}{\max{k,\ell}}(G\Box H)\leq {\rm la}{k}(G)+{\rm la}{\ell}(H)$ for any two graphs $G$ and $H$. Denote by $G\circ H$, $G\times H$ and $G⊠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 la}{k}(G\circ H)$,${\rm la}{k}(G\times H)$and${\rm la}_{k}(G\boxtimes H)$inthispaper\mathrm{.}Thelinear$k$-arboricityofa$2$-dimensionalgridgraph,a$r$-dimensionalmesh,a$r$-dimensionaltorus,a$r$-dimensional generalized hypercube and a $2$-dimensional hyper Petersen network are also studied.