On linear 2-arboricity of certain graphs

Jijuan Chen and Tao Wang

Applied Mathematics and Computation, 2023, vol. 441, issue C

Abstract: The linear 2-arboricity of a graph G is the least number of forests which decomposes E(G) and each forest is a collection of paths of length at most two. A graph has property Pk, if each subgraph H satisfies one of the three conditions: (i) δ(H)≤1; (ii) there exists xy∈E(H) with degH(x)+degH(y)≤k; (iii) H contains a 2-alternating cycle. In this paper, we give two edge-decompositions of graphs with property Pk. Using these decompositions, we give an upper bound for the linear 2-arboricity in terms of Pk. We also prove that every plane graph with no 12+-vertex incident with a gem at the center has property P13, and graphs with maximum average degree less than 6k−6k+3 have property Pk, where k≥5 is an integer.

Keywords: Linear 2-arboricity; Edge-decomposition; Plane graphs; Gem graph; Maximum average degree (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300322007603
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:441:y:2023:i:c:s0096300322007603

DOI: 10.1016/j.amc.2022.127692

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 ().