Graph toughness
Encyclopedia
In graph theory
, toughness is a measure of the connectivity
of a graph. A graph is said to be -tough for a given real number
if, for every integer
, cannot be split into different connected component
s by the removal of fewer than vertices. For instance, a graph is -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 for which it is -tough; this is a finite number for all graphs except the complete graph
s, which by convention have infinite toughness.
If a graph is -tough, then one consequence (obtained by setting ) is that any nodes can be removed without splitting the graph in two. That is, every -tough graph is also -vertex-connected
.
Graph toughness was first introduced by . He observed that every cycle
, and therefore every Hamiltonian graph, is -tough; that is, being -tough is a necessary condition for a graph to be Hamiltonian. Chvátal also made some other conjectures relating toughness to Hamiltonicity. Since then there has been extensive work by other mathematicians on toughness; the recent survey by lists 99 theorems and 162 papers on the subject.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, toughness is a measure of the connectivity
Connectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...
of a graph. A graph is said to be -tough for a given real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
if, for every integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
, cannot be split into different connected component
Connected component
Connected components are part of topology and graph theory, two related branches of mathematics.* For the graph-theoretic concept, see connected component .* In topology: connected component .Implementations:...
s by the removal of fewer than vertices. For instance, a graph is -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 for which it is -tough; this is a finite number for all graphs except the complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
s, which by convention have infinite toughness.
If a graph is -tough, then one consequence (obtained by setting ) is that any nodes can be removed without splitting the graph in two. That is, every -tough graph is also -vertex-connected
K-vertex-connected graph
In graph theory, a graph G with vertex set V is said to be k-vertex-connected if the graph remains connected when you delete fewer than k vertices from the graph...
.
Graph toughness was first introduced by . He observed that every cycle
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
, and therefore every Hamiltonian graph, is -tough; that is, being -tough is a necessary condition for a graph to be Hamiltonian. Chvátal also made some other conjectures relating toughness to Hamiltonicity. Since then there has been extensive work by other mathematicians on toughness; the recent survey by lists 99 theorems and 162 papers on the subject.