Graph toughness

In this graph, removing the four red vertices would produce four connected components. However, there is no set of k vertices whose removal leaves more than k components. Therefore, its toughness is exactly 1.

In graph theory, toughness is a measure of the connectivity of a graph. A graph G is said to be t-tough for a given real number t if, for every integer 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.

If a graph is t-tough, then one consequence (obtained 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; that is, being 1-tough is a necessary condition for a graph to be Hamiltonian. Chvátal also 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 & Schmiechel (2006) lists 99 theorems and 162 papers on the subject.

References

• Bauer, Douglas; Broersma, Hajo; Schmeichel, Edward (2006), "Toughness in graphs—a survey", Graphs and Combinatorics 22 (1): 1–35, doi:10.1007/s00373-006-0649-0, MR2221006 .
• Chvátal, Václav (1973), "Tough graphs and Hamiltonian circuits", Discrete Mathematics 5 (3): 215–228, doi:10.1016/0012-365X(73)90138-6, MR0316301 .