Title: The complexity of recognizing minimally tough graphs,
Abstract: 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. The complexity class DP is the set of
all languages that can be expressed as the intersection of a language in NP and
a language in coNP. We prove that recognizing minimally $t$-tough graphs is
DP-complete for any positive integer $t$ and for any positive rational number
$t \leq 1/2$.