Minimally toughness in special graph classes

Gyula Y. Katona, Kitti Varga

Published 2018-01-31Version 1

Let $t$ be a positive real number. A graph is called $t$-tough, if the removal of any cutset $S$ leaves at most $|S|/t$ components. The toughness of a graph is the largest $t$ for which the graph is $t$-tough. A graph is minimally $t$-tough, if the toughness of the graph is $t$ and the deletion of any edge from the graph decreases the toughness. In this paper we investigate the minimum degree and the recognizability of minimally $t$-tough graphs in the class of chordal graphs, split graphs, claw-free graphs and $2K_2$-free graphs.