Toughness in graphs - A survey

Douglas Bauer; Haitze J. Broersma; Edward Schmeichel

doi:10.1007/s00373-006-0649-0

Toughness in graphs - A survey

Douglas Bauer
, Haitze J. Broersma
, Edward Schmeichel

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

106 Citations (Scopus)

55 Downloads (Pure)

Abstract

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!

Original language	Undefined
Article number	10.1007/s00373-006-0649-0
Pages (from-to)	1-35
Number of pages	35
Journal	Graphs and combinatorics
Volume	22
Issue number	10/1
DOIs	https://doi.org/10.1007/s00373-006-0649-0
Publication status	Published - Apr 2006

Keywords

IR-63724
Hamiltonian graph
Chordal graph
(Hamilton) cycle
Factor
METIS-237666
Computational Complexity
Circumference
Traceable graph
Triangle-free graph
Toughness
EWI-8329
k-Factor
Planar graph
t-Tough graph

Access to Document

10.1007/s00373-006-0649-0

http://eprints.eemcs.utwente.nl/secure2/8329/01/bauer.pdf

Cite this

@article{ec8726487f3b44de9890376eb8252d5f,

title = "Toughness in graphs - A survey",

abstract = "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!",

keywords = "IR-63724, Hamiltonian graph, Chordal graph, (Hamilton) cycle, Factor, METIS-237666, Computational Complexity, Circumference, Traceable graph, Triangle-free graph, Toughness, EWI-8329, k-Factor, Planar graph, t-Tough graph",

author = "Douglas Bauer and Broersma, \{Haitze J.\} and Edward Schmeichel",

note = "10.1007/s00373-006-0649-0 ",

year = "2006",

month = apr,

doi = "10.1007/s00373-006-0649-0",

language = "Undefined",

volume = "22",

pages = "1--35",

journal = "Graphs and combinatorics",

issn = "0911-0119",

publisher = "Springer",

number = "10/1",

}

TY - JOUR

T1 - Toughness in graphs - A survey

AU - Bauer, Douglas

AU - Broersma, Haitze J.

AU - Schmeichel, Edward

N1 - 10.1007/s00373-006-0649-0

PY - 2006/4

Y1 - 2006/4

N2 - 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!

AB - 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!

KW - IR-63724

KW - Hamiltonian graph

KW - Chordal graph

KW - (Hamilton) cycle

KW - Factor

KW - METIS-237666

KW - Computational Complexity

KW - Circumference

KW - Traceable graph

KW - Triangle-free graph

KW - Toughness

KW - EWI-8329

KW - k-Factor

KW - Planar graph

KW - t-Tough graph

U2 - 10.1007/s00373-006-0649-0

DO - 10.1007/s00373-006-0649-0

M3 - Article

SN - 0911-0119

VL - 22

SP - 1

EP - 35

JO - Graphs and combinatorics

JF - Graphs and combinatorics

IS - 10/1

M1 - 10.1007/s00373-006-0649-0

ER -