The complexity of recognizing minimally tough graphs

Gyula Y Katona, István Kovács, Kitti Varga

A graph is called $t$-tough if the removal of any vertex set $S$ that disconnects the graph leaves at most $|S|/t$ components. The toughness of a graph is the largest $t$ for which…