Indexed by:
Abstract:
The 3-Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a set of cycles, and a matching. It has been proved independently by different groups of people that every connected cubic graph can be decomposed into a spanning tree, a set of cycles, and a set of vertex-disjoint paths of at most two edges. In this paper, we establish a bound on the number of paths of two edges, proving that every connected cubic graph on n vertices can be decomposed into a spanning tree, a set of cycles, and a set of vertex-disjoint paths of at most two edges such that the number of paths of two edges is at most [Formula presented]. Our proof is based on a structural analysis, which might provide a new approach to attack the 3-Decomposition Conjecture. © 2025 Elsevier B.V.
Keyword:
Reprint 's Address:
Email:
Source :
Discrete Mathematics
ISSN: 0012-365X
Year: 2025
Issue: 7
Volume: 348
0 . 7 0 0
JCR@2023
CAS Journal Grade:4
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: