Forbidden subgraphs, hamiltonicity and closure in claw-free graphs

被引：47
作者：
Brousek, J
Ryjacek, Z
Favaron, O
机构：
[1] Univ W Bohemia, Dept Math, Plzen 30614, Czech Republic
[2] Univ Paris Sud, CNRS, URA 410, LRI, F-91405 Orsay, France
来源：
DISCRETE MATHEMATICS | 1999年 / 196卷 / 1-3期
关键词：
subgraphs; Hamiltonian; undirected graphs;
D O I：
10.1016/S0012-365X(98)00334-3
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We study the stability of some classes of graphs defined in terms of forbidden subgraphs under the closure operation introduced by the second author. Using these results, we prove that every 2-connected claw-free and P-7-free, or claw-free and Z(4)-free, or claw-free and eiffel-free graph is either hamiltonian or belongs to a certain class of exceptions tall of them having connectivity 2). (C) 1999 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：29 / 50
页数：22
相关论文
共 15 条
  • [1] [Anonymous], 1990, CONT METHODS GRAPH T
  • [2] [Anonymous], 1981, THEORY APPL GRAPHS
  • [3] Bedrossian P., 1991, Forbidden subgraph and minimum degree conditions for hamiltonicity
  • [4] THE EDGE HAMILTONIAN PATH PROBLEM IS NP-COMPLETE
    BERTOSSI, AA
    [J]. INFORMATION PROCESSING LETTERS, 1981, 13 (4-5) : 157 - 159
  • [5] Bondy J.A., 1976, Graph Theory, V290
  • [6] BRANDT S, 1996, 23 U MEMPH
  • [7] BROUSEK J, IN PRESS DISCRETE MA
  • [8] Claw-free graphs - A survey
    Faudree, R
    Flandrin, E
    Ryjacek, Z
    [J]. DISCRETE MATHEMATICS, 1997, 164 (1-3) : 87 - 147
  • [9] Faudree R.J., 1995, J COMBIN MATH COMBIN, V19, P109
  • [10] Characterizing forbidden pairs for Hamiltonian properties
    Faudree, RJ
    Gould, RJ
    [J]. DISCRETE MATHEMATICS, 1997, 173 (1-3) : 45 - 60
12