• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Chu, Y. (Chu, Y..) [1] | Fan, G. (Fan, G..) [2] | Zhou, C. (Zhou, C..) [3]

Indexed by:

Scopus

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:

Gallai's conjecture Path decomposition Semi-cliques

Community:

  • [ 1 ] [Chu Y.]School of Mathematical Sciences, Suzhou University of Science and Technology, Jiangsu, 215009, China
  • [ 2 ] [Chu Y.]Key Laboratory of Discrete Mathematics with Applications of Ministry of Education, Fuzhou University, Fuzhou, 350116, China
  • [ 3 ] [Fan G.]Center for Discrete Mathematics, Fuzhou University, Fujian, 350108, China
  • [ 4 ] [Zhou C.]Center for Discrete Mathematics, Fuzhou University, Fujian, 350108, China

Reprint 's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

Discrete Mathematics

ISSN: 0012-365X

Year: 2026

Issue: 2

Volume: 349

0 . 7 0 0

JCR@2023

Cited Count:

WoS CC 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:

Online/Total:1534/13844372
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1