Circumferences of 3-connected claw-free graphs

被引：2
作者：
Chen, Zhi-Hong [1 ]
机构：
[1] Butler Univ, Indianapolis, IN 46208 USA
来源：
DISCRETE MATHEMATICS | 2016年 / 339卷 / 06期
关键词：
Circumference; Claw-free graph; Collapsible graph; Closed trail; Dominating closed trail; Supereulerian graph; SPANNING EULERIAN SUBGRAPHS;
D O I：
10.1016/j.disc.2016.01.018
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In Li et al. (2009), proved that a 3-connected claw-free graph of order n with minimum degree delta contains a cycle of length at least min{n, 6 delta - 15}, and they conjectured that such graphs should have a cycle of length at least min{n, 9 delta - 3}. We prove that this conjecture is true with delta >= 8. (C) 2016 Elsevier B.V. All rights reserved.
引用
收藏
页码：1640 / 1650
页数：11
相关论文
共 15 条
  • [1] [Anonymous], 1952, Proceedings of the London Mathematical Society, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]
  • [2] Bondy J., 2008, GRADUATE TEXTS MATH
  • [3] A REDUCTION METHOD TO FIND SPANNING EULERIAN SUBGRAPHS
    CATLIN, PA
    [J]. JOURNAL OF GRAPH THEORY, 1988, 12 (01) : 29 - 44
  • [4] Graphs without spanning closed trails
    Catlin, PA
    Han, ZY
    Lai, HJ
    [J]. DISCRETE MATHEMATICS, 1996, 160 (1-3) : 81 - 91
  • [5] Fan-Type Conditions for Spanning Eulerian Subgraphs
    Chen, Wei-Guo
    Chen, Zhi-Hong
    [J]. GRAPHS AND COMBINATORICS, 2015, 31 (06) : 2087 - 2102
  • [6] Eulerian subgraphs in 3-edge-connected graphs and Hamiltonian line graphs
    Chen, ZH
    Lai, HJ
    Li, XW
    Li, DY
    Mao, JZ
    [J]. JOURNAL OF GRAPH THEORY, 2003, 42 (04) : 308 - 319
  • [7] Harary F., 1965, Can. Math. Bull., V8, P701
  • [8] Hamiltonicity in 3-connected claw-free graphs
    Lai, Hong-Jian
    Shao, Yehong
    Zhan, Mingquan
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (04) : 493 - 504
  • [9] Circumferences and minimum degrees in 3-connected claw-free graphs
    Li, MingChu
    Cui, Yongrui
    Xiong, Liming
    Tian, Yuan
    Jiang, He
    Yuan, Xu
    [J]. DISCRETE MATHEMATICS, 2009, 309 (11) : 3580 - 3587
  • [10] Roussopoulos N. D., 1973, Information Processing Letters, V2, P108, DOI 10.1016/0020-0190(73)90029-X
12