Circumferences of regular claw-free graphs

被引：2
|
作者：
Li, MingChu [1 ]
机构：
[1] Chongqing Technol & Business Univ, Coll Sci, Chongqing 400067, Peoples R China
[2] Dalian Univ Technol, Sch Software, Dalian 116620, Liaoning, Peoples R China
来源：
DISCRETE MATHEMATICS | 2006年 / 306卷 / 21期
关键词：
circumference; longest cycle; claw-free graph; regularity; 3-connectedness;
D O I：
10.1016/j.disc.2006.04.026
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A known result obtained independently by Fan and Jung is that every 3-connected k-regular graph on n vertices contains a cycle of length at least min{3k, n}. This raises the question of how much can be said about the circumferences of 3-connected k-regular claw-free graphs. In this paper, we show that every 3-connected k-regular claw-free graph on n vertices contains a cycle of length at least min{6k - 17, n}. (c) 2006 Elsevier B.V. All rights reserved.
引用
收藏
页码：2682 / 2694
页数：13
相关论文
共 50 条
  • [41] Some classical combinatorial problems on circulant and claw-free graphs: the isomorphism and coloring problems on circulant graphs and the stable set problem on claw-free graphs
    Ugo Pietropaoli
    4OR, 2009, 7 : 297 - 300
  • [42] Some classical combinatorial problems on circulant and claw-free graphs: the isomorphism and coloring problems on circulant graphs and the stable set problem on claw-free graphs
    Pietropaoli, Ugo
    4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2009, 7 (03): : 297 - 300
  • [43] On Hamiltonicity of 3-Connected Claw-Free Graphs
    Runli Tian
    Liming Xiong
    Zhaohong Niu
    Graphs and Combinatorics, 2014, 30 : 1261 - 1269
  • [44] Hamiltonian claw-free graphs with locally disconnected vertices
    Tian, Runli
    Xiong, Liming
    DISCRETE MATHEMATICS, 2015, 338 (11) : 2042 - 2050
  • [45] Edge decomposition of connected claw-free cubic graphs
    Hong, Yanmei
    Liu, Qinghai
    Yu, Nannan
    DISCRETE APPLIED MATHEMATICS, 2020, 284 : 246 - 250
  • [46] Spectral Radius and Traceability of Connected Claw-Free Graphs
    Ning, Bo
    Li, Binlong
    FILOMAT, 2016, 30 (09) : 2445 - 2452
  • [47] The zero forcing number of claw-free cubic graphs
    He, Mengya
    Li, Huixian
    Song, Ning
    Ji, Shengjin
    DISCRETE APPLIED MATHEMATICS, 2024, 359 : 321 - 330
  • [48] On cycle lengths in claw-free graphs with complete closure
    Ryjacek, Zdenek
    Skupien, Zdzislaw
    Vrana, Petr
    DISCRETE MATHEMATICS, 2010, 310 (03) : 570 - 574
  • [49] Closure operation for even factors on claw-free graphs
    Xiong, Liming
    DISCRETE MATHEMATICS, 2011, 311 (16) : 1714 - 1723
  • [50] On hamiltonicity of 2-connected claw-free graphs
    Tian Run-li
    Xiong Li-ming
    APPLIED MATHEMATICS-A JOURNAL OF CHINESE UNIVERSITIES SERIES B, 2012, 27 (02) : 234 - 242
12345