Indexed by:
Abstract:
Let G be a graph with n vertices. A path decomposition of G is a set of edge-disjoint paths including all the edges of G. Let p(G) denote the minimum number of paths in a path decomposition of G. Gallai's Conjecture asserts that if G is connected, then [Formula prsented]. The E-subgraph of G is the subgraph induced by the vertices of even degree in G. A well-known result of Lovász is that if the E-subgraph of G is empty or isomorphic to K1, then [Formula prsented]. In this paper, we prove that if the E-subgraph of G is isomorphic to Km with m≤15, then [Formula prsented], which implies, under the condition, that Gallai's Conjecture holds when n is odd. A simple graph G on n vertices is called a semi-clique if [Formula prsented]. By the definition, if G is a semi-clique on n vertices, then n must be odd and [Formula prsented]. As a corollary of our main result, we obtain that if G is a semi-clique on n vertices, then [Formula prsented]. © 2025 Elsevier B.V.
Keyword:
Reprint 's Address:
Email:
Source :
Discrete Mathematics
ISSN: 0012-365X
Year: 2026
Issue: 2
Volume: 349
0 . 7 0 0
JCR@2023
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 2
Affiliated Colleges: