On the complexity of recognizing tough graphs (Q1313820)

Let G be an undirected graph without loops or multiple edges. Let V(G), \(\omega\)(G), and \(\delta\)(G) denote the vertex set, independence number, and minimum vertex degree of G. Let \(t\) be any positive real number. G is said to be \(t\)-tough if \(t\omega\)(G-- X)\(\leq |\)X\(|\) for all X\( \subseteq\)V(G) with \(\omega\)(G-X)\(\geq 2\). The authors consider the relationship between the minimum degree \(\delta\)(G) and the complexity of recognizing if a graph is \(t\)-tough. Specifically, they prove the following claims. (a) If \(\delta\)(G)\(\geq \text{tn}/(t + 1)\), then G is \(t\)-tough. (b) For any \(\varepsilon > 0\), it is NP-hard to determine if G is \(t\)- tough, even for the class of graphs with \(\delta\)(G)\(\geq (t/(t - 1) - \varepsilon)n\).