Strengthening some complexity results on toughness of graphs

Gyula Y Katona, Kitti Varga

Let $t$ be a positive real number. 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…