Back to Search
Start Over
Line k-Arboricity in Product Networks
- Publication Year :
- 2016
- Publisher :
- arXiv, 2016.
-
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 ${\rm 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\{{\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\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 la}_{k}(G\circ H)$, ${\rm la}_{k}(G\times H)$ and ${\rm la}_{k}(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.<br />Comment: 27 pages
- Subjects :
- FOS: Mathematics
Mathematics - Combinatorics
Combinatorics (math.CO)
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....6ce082769d46684688204e338a39de0b
- Full Text :
- https://doi.org/10.48550/arxiv.1603.04121