Supertough $5$-Regular Graphs

Abstract

The computation of the maximum toughness among graphs with $n$ vertices and $m$ edges is considered for $\lceil 5n/2\rceil \le m<3n$. We show that there are only finitely many cases in which the toughness value $\frac{5}{2}$ cannot be achieved. This is in stark contrast with the known result that there is a $\frac{3}{2}$-tough graph on $n$ vertices and $\lceil 3n/2\rceil$ edges if and only if $n\equiv 0,5(\mathrm{mod}6)$. However, constructions related to those used in the cubic case are also employed here. Our constructions additionally provide an infinite family of graphs that are supertough and not $K_{1,3}$-free.