The minimum degree of minimally $t$-tough graphs

Abstract

A graph $G$ is minimally $t$-tough if the toughness of $G$ is $t$ and deletion of any edge from $G$ decreases its toughness. Katona et al. conjectured that the minimum degree of any minimally $t$-tough graph is $\lceil 2t\rceil$ and gave some upper bounds on the minimum degree of the minimally $t$-tough graphs in \cite{Katona, Gyula}. In this paper, we show that a minimally 1-tough graph $G$ with girth $g\ge 5$ has minimum degree at most $\lfloor \frac{n}{g+1}\rfloor +g-1$, and a minimally $1$-tough graph with girth $4$ has minimum degree at most $\frac{n+6}{4}$. We also prove that the minimum degree of minimally $\frac{3}{2}$-tough claw-free graphs is $3$.

15pages