Английская Википедия:Graph toughness
In graph theory, toughness is a measure of the connectivity of a graph. A graph Шаблон:Math is said to be Шаблон:Math-tough for a given real number Шаблон:Mvar if, for every integer Шаблон:Math, Шаблон:Math cannot be split into Шаблон:Math different connected components by the removal of fewer than Шаблон:Math vertices. For instance, a graph is Шаблон: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 Шаблон:Math for which it is Шаблон: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 Шаблон:Harvs. Since then there has been extensive work by other mathematicians on toughness; the recent survey by Шаблон:Harvtxt lists 99 theorems and 162 papers on the subject.
Examples
Removing Шаблон:Mvar vertices from a path graph can split the remaining graph into as many as Шаблон: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 Шаблон:Sfrac-tough. In contrast, removing Шаблон:Mvar vertices from a cycle graph leaves at most Шаблон:Mvar remaining connected components, and sometimes leaves exactly Шаблон:Mvar connected components, so a cycle is Шаблон:Math-tough.
Connection to vertex connectivity
If a graph is Шаблон:Mvar-tough, then one consequence (obtained by setting Шаблон:Math) is that any set of Шаблон:Math nodes can be removed without splitting the graph in two. That is, every Шаблон:Mvar-tough graph is also [[k-vertex-connected graph|Шаблон:Math-vertex-connected]].
Connection to Hamiltonicity
Шаблон:Unsolved Шаблон:Harvtxt observed that every cycle, and therefore every Hamiltonian graph, is Шаблон:Math-tough; that is, being Шаблон: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 Шаблон:Mvar such that every Шаблон:Mvar-tough graph is Hamiltonian. Chvátal's original conjecture that Шаблон:Math would have proven Fleischner's theorem but was disproved by Шаблон: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 Шаблон:Math-tough is co-NP-complete. That is, the decision problem whose answer is "yes" for a graph that is not 1-tough, and "no" for a graph that is 1-tough, is NP-complete. The same is true for any fixed positive rational number Шаблон:Mvar: testing whether a graph is Шаблон:Mvar-tough is co-NP-complete Шаблон: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
References
