Maximum Toughness Among \((n, m)\)-Graphs

The maximum possible toughness among graphs with \(n\) vertices and \(m\) edges is considered. This is an analog of the corresponding problem regarding maximum connectivity solved by Harary. We show that, if \(m < \lceil \frac{3n}{2} \rceil\) or \(m \geq n(\lfloor \frac{n}{6} \rfloor + \lfloor \frac{n \mod 6}{3} \rfloor)\), then the maximum toughness is half of the maximum connectivity. The same conclusion is obtained if \(r = \lfloor \frac{2m}{n} \rfloor \geq 1\) and \(\frac{(n-1)(r+1)}{2} \leq m < \frac{n(r+1)}{2}\). However, maximum toughness can be strictly less than half of maximum connectivity. Some values of maximum toughness are computed for \(1 \leq n \leq 12\), and some open problems are presented