Graph toughness
In
Graph toughness was first introduced by Václav Chvátal (1973). Since then there has been extensive work by other mathematicians on toughness; the recent survey by Bauer, Broersma & Schmeichel (2006) lists 99 theorems and 162 papers on the subject.
Examples
Removing k vertices from a path graph can split the remaining graph into as many as k + 1 connected components. The maximum ratio of components to removed vertices is achieved by removing one vertex (from the interior of the path) and splitting it into two components. Therefore, paths are 1/2-tough. In contrast, removing k vertices from a cycle graph leaves at most k remaining connected components, and sometimes leaves exactly k connected components, so a cycle is 1-tough.
Connection to vertex connectivity
If a graph is t-tough, then one consequence (obtained by setting k = 2) is that any set of 2t − 1 nodes can be removed without splitting the graph in two. That is, every t-tough graph is also 2t-vertex-connected.
Connection to Hamiltonicity
Is there a number such that every -tough graph is Hamiltonian?
Computational complexity
Testing whether a graph is 1-tough is
See also
- Strength of a graph, an analogous concept for edge deletions
- Tutte–Berge formula, a related characterization of the size of a maximum matching in a graph
References
- Bauer, Douglas; Broersma, Hajo; Schmeichel, Edward (2006), "Toughness in graphs—a survey", S2CID 3237188.
- Bauer, D.; Broersma, H. J.; Veldman, H. J. (2000), "Not every 2-tough graph is Hamiltonian", Proceedings of the 5th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1997), MR 1743840.
- Bauer, D.; MR 1074858.
- MR 0316301.