Line k-Arboricity in Product Networks

Abstract

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 ${\mathrm{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 \{{\mathrm{la}}_k(G),{\mathrm{la}}_{\ell }(H)\}\le {\mathrm{la}}_{\max \{k,\ell \}}(G\square H)\le {\mathrm{la}}_k(G)+{\mathrm{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 ${\mathrm{la}}_k(G\circ H)$, ${\mathrm{la}}_k(G\times H)$ and ${\mathrm{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 $2$-dimensional hyper Petersen network are also studied.

27 pages