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 条
  • [41] Total restrained domination in claw-free graphs
    Hongxing Jiang
    Liying Kang
    Journal of Combinatorial Optimization, 2010, 19 : 60 - 68
  • [42] Induced Nets and Hamiltonicity of Claw-Free Graphs
    Chiba, Shuya
    Fujisawa, Jun
    GRAPHS AND COMBINATORICS, 2021, 37 (03) : 663 - 690
  • [43] Local Clique Covering of Claw-Free Graphs
    Javadi, Ramin
    Maleki, Zeinab
    Omoomi, Behnaz
    JOURNAL OF GRAPH THEORY, 2016, 81 (01) : 92 - 104
  • [44] Induced Nets and Hamiltonicity of Claw-Free Graphs
    Shuya Chiba
    Jun Fujisawa
    Graphs and Combinatorics, 2021, 37 : 663 - 690
  • [45] Upper total domination in claw-free graphs
    Favaron, O
    Henning, MA
    JOURNAL OF GRAPH THEORY, 2003, 44 (02) : 148 - 158
  • [46] Strongly Spanning Trailable Graphs with Small Circumference and Hamilton-Connected Claw-Free Graphs
    Liu, Xia
    Xiong, Liming
    Lai, Hong-Jian
    GRAPHS AND COMBINATORICS, 2021, 37 (01) : 65 - 85
  • [47] Edge clique cover of claw-free graphs
    Javadi, Ramin
    Hajebi, Sepehr
    JOURNAL OF GRAPH THEORY, 2019, 90 (03) : 311 - 405
  • [48] On the choice number of claw-free perfect graphs
    Gravier, S
    Maffray, F
    DISCRETE MATHEMATICS, 2004, 276 (1-3) : 211 - 218
  • [49] Total restrained domination in claw-free graphs
    Jiang, Hongxing
    Kang, Liying
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2010, 19 (01) : 60 - 68
  • [50] INDUCED DISJOINT PATHS IN CLAW-FREE GRAPHS
    Golovach, Petr A.
    Paulusma, Daniel
    Van Leeuwen, Erik Jan
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2015, 29 (01) : 348 - 375
12345