- Graph toughness
In
graph theory , toughness is a measure of theconnectivity of a graph. A graph "G" is said to be "t"-tough if, for every "k" > 1, "G" cannot be split into "k" different connected components by the removal of fewer than "tk" vertices. For instance, a graph is 1-tough if the number of components formed by removing a set of vertices is always at most as large as the number of removed vertices. The toughness of a graph is the maximum "t" for which it is "t"-tough; this is a finite number for all graphs except thecomplete graph s, which by convention have infinite toughness.One consequence of "t"-toughness (by setting "k" = 2) is that any 2"t" − 1 nodes can be removed without splitting the graph in two. That is, every "t"-tough graph is also 2"t"-vertex-connected.
Graph toughness was first introduced by
Václav Chvátal (1973). He observed that every cycle, and therefore everyHamiltonian graph , is 1-tough, and made some other conjectures relating toughness to Hamiltonicity. Since then there has been extensive work by other mathematicians on toughness; the recent survey by Bauer, Broersma, and Schmiechel (2006) lists 99 theorems and 162 papers on the subject.References
*cite journal
author = Bauer, Douglas; Broersma, Hajo; Schmeichel, Edward
title = Toughness in graphs—a survey
journal = Graphs and Combinatorics
volume = 22
year = 2006
issue = 1
pages = 1–35
id = MathSciNet | id = 2221006
doi = 10.1007/s00373-006-0649-0*cite journal
author = Chvátal, Václav
authorlink = Václav Chvátal
title = Tough graphs and Hamiltonian circuits
journal = Discrete Mathematics
volume = 5
issue = 3
year = 1973
pages = 215–228
id = MathSciNet | id = 0316301
doi = 10.1016/0012-365X(73)90138-6
Wikimedia Foundation. 2010.
