Indexed by:
Abstract:
Let G be a graph with n vertices. A path decomposition of G is a set of edge-disjoint paths containing all the edges of G. Let p(G) denote the minimum number of paths needed in a path decomposition of G. Gallai Conjecture asserts that if G is connected, then p(G)≤⌈n/2⌉. If G is allowed to be disconnected, then the upper bound [Formula presented] for p(G) was obtained by Donald [7], which was improved to [Formula presented] independently by Dean and Kouider [6] and Yan [14]. For graphs consisting of vertex-disjoint triangles, [Formula presented] is reached and so this bound is tight. If triangles are forbidden in G, then [Formula presented] can be derived from the result of Harding and McGuinness [11], where g denotes the girth of G. In this paper, we also focus on triangle-free graphs and prove that p(G)≤⌊3n/5⌋, which improves the above result with g=4. © 2022 Elsevier B.V.
Keyword:
Reprint 's Address:
Email:
Source :
Discrete Mathematics
ISSN: 0012-365X
Year: 2022
Issue: 7
Volume: 345
0 . 8
JCR@2022
0 . 7 0 0
JCR@2023
ESI HC Threshold:24
JCR Journal Grade:3
CAS Journal Grade:3
Cited Count:
SCOPUS Cited Count: 1
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: