Karl Jones: Created page with "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 i..."

2016-09-09T18:39:58Z

Created page with "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 i..."

New page

In [[graph theory]], '''toughness''' is a measure of the connectivity of a [[Graph (discrete mathematics)|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 ==

* [https://en.wikipedia.org/wiki/Graph_toughness Graph toughness] @ Wikipedia

[[Category:Mathematics]]

Graph toughness - Revision history

Karl Jones: Created page with "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 i..."