Forbidden subgraphs, hamiltonicity and closure in claw-free graphs

被引：48
作者：
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 [J].
BERTOSSI, AA .
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 [J].
Faudree, R ;
Flandrin, E ;
Ryjacek, Z .
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 [J].
Faudree, RJ ;
Gould, RJ .
DISCRETE MATHEMATICS, 1997, 173 (1-3) :45-60
12