Graph toughness

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.

Description

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.

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.

See also

• Graph (discrete mathematics)
• Graph theory
• Tutte–Berge formula, a related characterization of the size of a maximum matching in a graph

External links

• Graph toughness @ Wikipedia