This MedLibrary.org supplementary page on Graph toughness is provided directly from the open source Wikipedia as a service to our readers. Please see the note below on authorship of this content, as well as the Wikipedia usage guidelines. To search for other content from our encyclopedia supplement, please use the form below:
Related Sponsors
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.
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}
Wikipedia content modification information:
- This page was last modified on 22 May 2007, at 23:18.
Wikipedia Authorship and Review
Wikipedia content provided here is not reviewed directly by MedLibrary.org. Wikipedia content is authored by an open community of volunteers and is not produced by or in any way affiliated with MedLibrary.org.
Wikipedia Usage Guidelines
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Graph toughness".
The URL for this specific entry is:
All Wikipedia text is available under the terms of the GNU Free Documentation License. (See Copyrights for details). Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc.