Claw-free 3-connected P11-free graphs are Hamiltonian

被引：13
|
作者：
Luczak, T [1 ]
Pfender, F
机构：
[1] Adam Mickiewicz Univ, Dept Discrete Math, PL-61614 Poznan, Poland
[2] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30322 USA
来源：
JOURNAL OF GRAPH THEORY | 2004年 / 47卷 / 02期
关键词：
Hamilton cycle; claw-free graphs; forbidden subgraphs;
D O I：
10.1002/jgt.20019
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We show that every 3-connected claw-free graph which contains no induced copy of P-11 is hamiltonian. Since there exist non-hamiltonian 3-connected claw-free graphs without induced copies of P-12 this result is, in a way, best possible. (C) 2004 Wiley Periodicals, Inc.
引用
收藏
页码：111 / 121
页数：11
相关论文
共 50 条
  • [21] Hamiltonian properties of 3-connected {claw,hourglass}-free graphs
    Ryjacek, Zdenek
    Vrana, Petr
    Xiong, Liming
    DISCRETE MATHEMATICS, 2018, 341 (06) : 1806 - 1815
  • [22] Every 3-Connected Claw-Free Z8-Free Graph Is Hamiltonian
    Lai, Hong-Jian
    Xiong, Liming
    Yan, Huiya
    Yan, Jin
    JOURNAL OF GRAPH THEORY, 2010, 64 (01) : 1 - 11
  • [23] Minimum degree conditions for the Hamiltonicity of 3-connected claw-free graphs
    Chen, Zhi-Hong
    Lai, Hong-Jian
    Xiong, Liming
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2017, 122 : 167 - 186
  • [24] ON HAMILTONIAN CLAW-FREE GRAPHS
    FLANDRIN, E
    FOUQUET, JL
    LI, H
    DISCRETE MATHEMATICS, 1993, 111 (1-3) : 221 - 229
  • [25] On 2-factors with long cycles in 3-connected claw-free graphs
    Chen, Zhi-Hong
    DISCRETE MATHEMATICS, 2024, 347 (10)
  • [26] Longest Cycles in 3-Connected k-Regular Claw-Free Graphs
    李国君
    数学进展, 1993, (01) : 88 - 89
  • [27] Hamiltonian Cycles in 2-Connected Claw-Free Graphs
    Li Mingchu (Department of Mathematics
    新疆大学学报(自然科学版), 1999, (01) : 2 - 14
  • [28] Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
    Bilinski, Mark
    Jackson, Bill
    Ma, Jie
    Yu, Xingxing
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2011, 101 (04) : 214 - 236
  • [29] Every 3-connected claw-free graph with domination number at most 3 is hamiltonian-connected
    Vrana, Petr
    Zhan, Xingzhi
    Zhang, Leilei
    DISCRETE MATHEMATICS, 2022, 345 (08)
  • [30] Hamiltonian properties of almost locally connected claw-free graphs
    Chen, Xiaodong
    Li, MingChu
    Liao, Wei
    Broersma, Hajo
    ARS COMBINATORIA, 2016, 124 : 95 - 109
12345