The linear (n−1)-arboricity of some lexicographic product graphs

摘要

A linear k-forest of an undirected graph G is a subgraph of G whose components are paths with lengths at most k. The linear k-arboricity of G, denoted by lak(G), is the minimum number of linear k-forests needed to partition the edge set E(G) of G. In this paper, the exact values of the linear (n−1)-arboricity of lexicographic product graphs Kn ○ Kn, n and Kn, n ○ Kn are obtained. Furthermore, lak(Kn,n□Kn,n) are also derived for the Cartesian product graph of two copies of Kn, n. These results confirm the conjecture about the upper bound lak(G) given in [Discrete Math. 41(1982)219-220] for Kn ○ Kn, n, Kn, n ○ Kn and Kn,n□Kn,n.