Toughness of a graph

Toughness of a graph --- жесткость графа.

The toughness [math]\displaystyle{ t(G) }[/math] of a graph [math]\displaystyle{ G }[/math] (where [math]\displaystyle{ G }[/math] is not a complete graph) is defined (Chvat\'{a}l, 1973) by

[math]\displaystyle{ t(G) = \min_{W}\frac{|W|}{c(G - W)}, }[/math]

where [math]\displaystyle{ W }[/math] is a cutset of [math]\displaystyle{ G }[/math] and [math]\displaystyle{ c(G - W) }[/math] denotes the number of connected components of the graph [math]\displaystyle{ G - W }[/math]. It is well known that a hamiltonian graph has toughness at least 1 and pseudo-[math]\displaystyle{ h }[/math]-hamiltonian graph has toughness at least [math]\displaystyle{ \frac{1}{h} }[/math].