On the complexity of recognizing tough graphs

AbstractWe consider the relationship between the minimum degree δ of a graph and the complexity of recognizing if a graph is t-tough. Let t⩾1 be a rational number. We first show that if δ(G)⩾tn/(t+1), then G is t-tough. On the other hand, for any fixed ε>0, we show that it is NP-hard to determine if G is t-tough, even for the class of graphs with δ(G)⩾(t/(t+1)−ε)n. In particular, for any fixed c