Speaker
Description
For a non-negative real number $t$, a graph $G$ is called $t$-tough if for every vertex set $S \subseteq V(G)$ that separates $G$, we have $t \cdot c(G-S) \leq |S|$, where $c(G-S)$ is the number of components of $G-S$. The toughness of a non-complete graph is the largest $t$ for which the graph is $t$-tough, while the toughness of complete graphs is infinity. The concept of toughness was introduced and studied in connection with Hamiltonicity, as every Hamiltonian graph is $1$-tough.
A graph $G$ is minimally $t$-tough if the toughness of $G$ is $t$ and the removal of any edge from $G$ decreases the toughness. A graph is minimally tough if it is complete or minimally $t$-tough for some real number $t$. Although deciding if a graph is minimally tough is a difficult problem in general, minimally tough graphs have been characterized in some graph classes. We characterize minimally tough graphs in the classes of $P_4$-free graphs, complete multipartite graphs, and complements of forests. We also characterize minimally tough co-chordal graphs whose complement has diameter at least $3$.
