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 条
  • [31] Clique minors in claw-free graphs
    Fradkin, Alexandra
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2012, 102 (01) : 71 - 85
  • [32] Colouring Squares of Claw-free Graphs
    de Verclos, Remi de Joannis
    Kang, Ross J.
    Pastor, Lucas
    CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 2019, 71 (01): : 113 - 129
  • [33] Full cycle extendability of triangularly connected almost claw-free graphs
    Zhan, Mingquan
    ARS COMBINATORIA, 2010, 96 : 489 - 497
  • [34] Traceability in small claw-free graphs
    Harris, John M.
    Mossinghoff, Michael J.
    UTILITAS MATHEMATICA, 2006, 70 : 263 - 271
  • [35] SEMITOTAL DOMINATION IN CLAW-FREE GRAPHS
    Chen, Jie
    Liang, Yi-Ping
    Xu, Shou-Jun
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2024, 44 (04) : 1585 - 1605
  • [36] Claw-free graphs are not universal fixers
    Cockayne, E. J.
    Gibson, R. G.
    Mynhardt, C. M.
    DISCRETE MATHEMATICS, 2009, 309 (01) : 128 - 133
  • [37] Coloring vertices of claw-free graphs in three colors
    Lozin, Vadim
    Purcell, Christopher
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2014, 28 (02) : 462 - 479
  • [38] On 3-connected hamiltonian line graphs
    Chen, Ye
    Fan, Suohai
    Lai, Hong-Jian
    DISCRETE MATHEMATICS, 2012, 312 (11) : 1877 - 1882
  • [39] On the stability number of claw-free P5-free and more general graphs
    Brandstädt, A
    Hammer, PL
    DISCRETE APPLIED MATHEMATICS, 1999, 95 (1-3) : 163 - 167
  • [40] Smallest Odd Holes in Claw-Free Graphs
    Shrem, Shimon
    Stern, Michal
    Golumbic, Martin Charles
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2010, 5911 : 329 - +
12345