Claw-free graphs - A survey

被引:168
作者
Faudree, R
Flandrin, E
Ryjacek, Z
机构
[1] MEMPHIS STATE UNIV, DEPT MATH SCI, MEMPHIS, TN 38152 USA
[2] UNIV PARIS 11, LRI, URA 410 CNRS, F-91405 ORSAY, FRANCE
[3] UNIV W BOHEMIA, DEPT MATH, PLZEN, CZECH REPUBLIC
关键词
D O I
10.1016/S0012-365X(96)00045-3
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In this paper we summarize known results on claw-free graphs. The paper is subdivided into the following chapters and sections: 1. Introduction 2. Paths, cycles, hamiltonicity (a) Preliminaries (b) Degree and neighborhood conditions (c) Local connectivity conditions (d) Further forbidden subgraphs (e) Invariants (f) Squares (g) Regular graphs (h) Other hamiltonicity related results and generalizations 3. Matchings and factors 4. Independence, domination, other invariants and extremal problems 5. Algorithmic aspects 6. Miscellaneous 7. Appendix - List of all 2-connected nonhamiltonian claw-free graphs on n less than or equal to 12 vertices.
引用
收藏
页码:87 / 147
页数:61
相关论文
共 198 条
[1]  
AINOUCHE A, 1990, ARS COMBINATORIA, V29C, P110
[2]  
AINOUCHE A, HAMILTONIAN TRACEABL
[3]   FACTORS AND FACTORIZATIONS OF GRAPHS - A SURVEY [J].
AKIYAMA, J ;
KANO, M .
JOURNAL OF GRAPH THEORY, 1985, 9 (01) :1-42
[4]   DOMINATION AND INDEPENDENT DOMINATION NUMBERS OF A GRAPH [J].
ALLAN, RB ;
LASKAR, R .
DISCRETE MATHEMATICS, 1978, 23 (02) :73-76
[5]   THE MONOTONE CIRCUIT COMPLEXITY OF BOOLEAN FUNCTIONS [J].
ALON, N ;
BOPPANA, RB .
COMBINATORICA, 1987, 7 (01) :1-22
[6]  
AMBARTSUMIAN OA, 1990, DOKL AKAD NAUK ARMEN, V91, P19
[7]  
[Anonymous], 1990, CONT METHODS GRAPH T
[8]  
Asratian A.S., 1990, J COMB THEORY B, V49, P287
[9]  
ASRATIAN AS, GRAPHS SATISFYING LO
[10]  
Balakrishnan Rangaswami, 1986, P 17 SE INT C COMBIN, V53, P71