Toughness in graphs - A survey

被引：83
作者：
Bauer, D [1 ]
Broersma, H
Schmeichel, E
机构：
[1] Stevens Inst Technol, Dept Math Sci, Hoboken, NJ 07030 USA
[2] Univ Durham, Dept Comp Sci, Durham DH1 3LE, England
[3] Nankai Univ, Ctr Combinator, Tianjin 300071, Peoples R China
[4] San Jose State Univ, Dept Math, San Jose, CA 95192 USA
来源：
GRAPHS AND COMBINATORICS | 2006年 / 22卷 / 01期
关键词：
toughness; t-tough graph; Hamilton cycle; Hamiltonian graph; traceable graph; circumference; factor; k-factor; chordal graph; triangle-free graph; planar graph; computational complexity;
D O I：
10.1007/s00373-006-0649-0
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In this survey we have attempted to bring together most of the results and papers that deal with toughness related to cycle structure. We begin with a brief introduction and a section on terminology and notation, and then try to organize the work into a few self explanatory categories. These categories are circumference, the disproof of the 2-tough conjecture, factors, special graph classes, computational complexity, and miscellaneous results as they relate to toughness. We complete the survey with some tough open problems!
引用
收藏
页码：1 / 35
页数：35
相关论文
共 150 条
[1]  
AINOUCHE A, 1985, J LOND MATH SOC, V32, P385
[2]   TOUGH RAMSEY GRAPHS WITHOUT SHORT CYCLES [J].
ALON, N .
JOURNAL OF ALGEBRAIC COMBINATORICS, 1995, 4 (03) :189-195
[3]  
[Anonymous], 1954, AM J MATH
[4]  
Badian E., 1989, ZPE, V79, P59
[5]  
Balakrishnan Rangaswami, 1986, P 17 SE INT C COMBIN, V53, P71
[6]  
Barefoot C., 1987, J Comb Math Comb Comput, V1, P12
[7]   A note on dominating cycles in 2-connected graphs [J].
Bauer, D ;
Schmeichel, E ;
Veldman, HJ .
DISCRETE MATHEMATICS, 1996, 155 (1-3) :13-18
[8]   The complexity of recognizing tough cubic graphs [J].
Bauer, D ;
vandenHeuvel, J ;
Morgana, A ;
Schmeichel, E .
DISCRETE APPLIED MATHEMATICS, 1997, 79 (1-3) :35-44
[9]  
Bauer D, 1996, J GRAPH THEOR, V21, P405
[10]   A SIMPLE PROOF OF A THEOREM OF JUNG [J].
BAUER, D ;
MORGANA, A ;
SCHMEICHEL, EF .
DISCRETE MATHEMATICS, 1990, 79 (02) :147-152
12345678910