Toughness in graphs - A survey

Douglas Bauer, Haitze J. Broersma, Edward Schmeichel

Research output: Contribution to journalArticleAcademicpeer-review

57 Citations (Scopus)

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 languageUndefined
Article number10.1007/s00373-006-0649-0
Pages (from-to)1-35
Number of pages35
JournalGraphs and combinatorics
Volume22
Issue number10/1
DOIs
Publication statusPublished - 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

Cite this

Bauer, D., Broersma, H. J., & Schmeichel, E. (2006). Toughness in graphs - A survey. Graphs and combinatorics, 22(10/1), 1-35. [10.1007/s00373-006-0649-0]. https://doi.org/10.1007/s00373-006-0649-0