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

Shengjie He, Rong-Xia Hao and Liancui Zuo

Applied Mathematics and Computation, 2018, vol. 338, issue C, 152-163

Abstract: 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.

Keywords: Linear k-arboricity; Cartesian product graph; Lexicographic product graph; Bipartite difference (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300318304958
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:338:y:2018:i:c:p:152-163

DOI: 10.1016/j.amc.2018.06.007

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().