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) <= inverted right perpendicularn/2inverted left perpendicular. If G is allowed to be disconnected, then the upper bound left perpendicular3/4nright perpendicular for p(G) was obtained by Donald [7], which was improved to left perpendicular2/3nright perpendicular independently by Dean and Kouider [6] and Yan [14]. For graphs consisting of vertex-disjoint triangles, left perpendicular2/3nright perpendicular is reached and so this bound is tight. If triangles are forbidden in G, then p(G) <= left perpendicularg+1/2g nright perpendicular 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) <= left perpendicular3n/5right perpendicular, which improves the above result with g = 4. (C) 2022 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
DISCRETE MATHEMATICS
ISSN: 0012-365X
Year: 2022
Issue: 7
Volume: 345
0 . 8
JCR@2022
0 . 7 0 0
JCR@2023
ESI Discipline: MATHEMATICS;
ESI HC Threshold:24
JCR Journal Grade:3
CAS Journal Grade:3
Cited Count:
WoS CC Cited Count: 1
SCOPUS Cited Count: 1
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: