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

author:

Chu, Yanan (Chu, Yanan.) [1] | Fan, Genghua (Fan, Genghua.) [2] (Scholars:范更华) | Zhou, Chuixiang (Zhou, Chuixiang.) [3] (Scholars:周垂香)

Indexed by:

Scopus SCIE

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:

Decomposition Gallai & rsquo;s conjecture Path Triangle-free

Community:

  • [ 1 ] [Chu, Yanan]Suzhou Univ Sci & Technol, Coll Math, Suzhou 215009, Peoples R China
  • [ 2 ] [Fan, Genghua]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350108, Fujian, Peoples R China
  • [ 3 ] [Zhou, Chuixiang]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350108, Fujian, Peoples R China

Reprint 's Address:

Show more details

Version:

Related Keywords:

Related Article:

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

Online/Total:149/10032893
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