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

{m l a}_{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

m a x {m l a}_{k} (G), {m l a}_{e l l} (H) l e q {m l a}_{m a x k, e l l} (G B o x H) l e q {m l a}_{k} (G) + {m l a}_{e l l} (H)

for any two graphs

G

and

H

. Denote by

G c i r c H

,

G i m e s H

and

the lexicographic product, direct product and strong product of two graphs

G

and

H

, respectively. We also derive upper and lower bounds of

{m l a}_{k} (G c i r c H)

,

{m l a}_{k} (G i m e s H)

and

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.

This page was built for publication: Line k-Arboricity in Product Networks