Contents

-

Maximum Toughness Among (n,m)-Graphs

Kevin Ferland1
1Bloomsburg University, Bloomsburg, PA 17815

Abstract

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<3n2 or mn(n6+nmod63), then the maximum toughness is half of the maximum connectivity. The same conclusion is obtained if r=2mn1 and (n1)(r+1)2m<n(r+1)2. However, maximum toughness can be strictly less than half of maximum connectivity. Some values of maximum toughness are computed for 1n12, and some open problems are presented