Graph toughness

In this graph, removing the four red vertices would produce four connected components (depicted in four different colours). 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 Template:Math is said to be Template:Math-tough for a given real number Template:Mvar if, for every integer Template:Math, Template:Math cannot be split into Template:Math different connected components by the removal of fewer than Template:Math vertices. For instance, a graph is Template:Math-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 Template:Math for which it is Template:Math-tough; this is a finite number for all finite graphs except the complete graphs, which by convention have infinite toughness.

Graph toughness was first introduced by Template:Harvs. Since then there has been extensive work by other mathematicians on toughness; the recent survey by Template:Harvtxt lists 99 theorems and 162 papers on the subject.

Examples

Removing Template:Mvar vertices from a path graph can split the remaining graph into as many as Template:Math 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 Template:Sfrac-tough. In contrast, removing Template:Mvar vertices from a cycle graph leaves at most Template:Mvar remaining connected components, and sometimes leaves exactly Template:Mvar connected components, so a cycle is Template:Math-tough.

Connection to vertex connectivity

If a graph is Template:Mvar-tough, then one consequence (obtained by setting Template:Math) is that any set of Template:Math nodes can be removed without splitting the graph in two. That is, every Template:Mvar-tough graph is also [[k-vertex-connected graph|Template:Math-vertex-connected]].

Connection to Hamiltonicity

Template:Unsolved Template:Harvtxt observed that every cycle, and therefore every Hamiltonian graph, is Template:Math-tough; that is, being Template:Math-tough is a necessary condition for a graph to be Hamiltonian. He conjectured that the connection between toughness and Hamiltonicity goes in both directions: that there exists a threshold Template:Mvar such that every Template:Mvar-tough graph is Hamiltonian. Chvátal's original conjecture that Template:Math would have proven Fleischner's theorem but was disproved by Template:Harvtxt. The existence of a larger toughness threshold for Hamiltonicity remains open, and is sometimes called Chvátal's toughness conjecture.

Computational complexity

Testing whether a graph is Template:Math-tough is co-NP-complete. That is, the decision problem whose answer is "yes" for a graph that is not Template:Math-tough, and "no" for a graph that is Template:Math-tough, is NP-complete. The same is true for any fixed positive rational number Template:Mvar: testing whether a graph is Template:Mvar-tough is co-NP-complete Template:Harv.

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
• Harris graphs, a family of graphs that are tough, Eulerian, and non-Hamiltonian

References

• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.