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 条
  • [31] The structure of even factors in claw-free graphs
    Xiong, Liming
    Lu, Mei
    Han, Longsheng
    DISCRETE MATHEMATICS, 2009, 309 (08) : 2417 - 2423
  • [32] Claw-free minimal matching covered graphs
    Zhang, Yipei
    Wang, Xiumei
    Yuan, Jinjiang
    Ng, C. T.
    Cheng, T. C. E.
    DISCRETE APPLIED MATHEMATICS, 2025, 370 : 11 - 21
  • [33] The Cycle Spectrum of Claw-free Hamiltonian Graphs
    Jonas Eckert
    Felix Joos
    Dieter Rautenbach
    Graphs and Combinatorics, 2016, 32 : 93 - 101
  • [34] Extremal problems on the Hamiltonicity of claw-free graphs
    Li, Binlong
    Ning, Bo
    Peng, Xing
    DISCRETE MATHEMATICS, 2018, 341 (10) : 2774 - 2788
  • [35] Depth first search in claw-free graphs
    Wiener, Gabor
    OPTIMIZATION LETTERS, 2018, 12 (02) : 367 - 373
  • [36] On cycle-nice claw-free graphs
    Zhang, Shanshan
    Wang, Xiumei
    Yuan, Jinjiang
    Ng, C. T.
    Cheng, T. C. E.
    DISCRETE MATHEMATICS, 2022, 345 (07)
  • [37] Connected even factors in claw-free graphs
    Lia, MingChu
    Xiong, Liming
    Broersma, H. J.
    DISCRETE MATHEMATICS, 2008, 308 (11) : 2282 - 2284
  • [38] Depth first search in claw-free graphs
    Gábor Wiener
    Optimization Letters, 2018, 12 : 367 - 373
  • [39] ON HAMILTONIAN CYCLES IN CLAW-FREE CUBIC GRAPHS
    Mohr, Elena
    Rautenbach, Dieter
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2022, 42 (01) : 309 - 313
  • [40] Paired-Domination in Claw-Free Graphs
    Shenwei Huang
    Liying Kang
    Erfang Shan
    Graphs and Combinatorics, 2013, 29 : 1777 - 1794
12345