Graph toughness
From Wikipedia, the free encyclopedia
In graph theory, toughness is a measure of the connectivity 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 the complete graphs, which by convention have infinite toughness.
One consequence of t-toughness (by setting k = 2) is that any 2t − 1 nodes can be removed without splitting the graph in two. That is, every t-tough graph is also 2t-vertex-connected.
Graph toughness was first introduced by Václav Chvátal (1973). He observed that every cycle, and therefore every Hamiltonian 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.
[edit] References
- Bauer, Douglas; Broersma, Hajo; Schmeichel, Edward (2006). "Toughness in graphs—a survey". Graphs and Combinatorics 22 (1): 1–35. doi:. MR2221006.
- Chvátal, Václav (1973). "Tough graphs and Hamiltonian circuits". Discrete Mathematics 5 (3): 215–228. doi:. MR0316301.
.svg){kind=small}
