The Maximum Toughness of Sesqui-Cubic Graphs

Abstract

We explore the maximum possible toughness among graphs with $n$ vertices and $m$ edges in the cases in which $\lceil \frac{3n}{2}\rceil \le m<2n$. In these cases, it is shown that the maximum toughness lies in the interval $[\frac{4}{3},\frac{3}{2}]$. Moreover, if $\lceil \frac{3n}{2}\rceil +2\le m<2n$, then the value $\frac{3}{2}$ is achieved. However, if $m\in \{\lceil \frac{3n}{2}\rceil ,\lceil \frac{3n}{2}\rceil +1\}$, then the maximum toughness can be strictly less than $\frac{3}{2}$. This provides an infinite family of graphs for which the maximum toughness is not half of the maximum connectivity. The values of maximum toughness are computed for all $1\le n\le 12$, and some open problems are presented.