ON SIZE, ORDER, DIAMETER AND VERTEX-CONNECTIVITY

Abstract

Let G be a nite connected graph. We give an asymptotically sharp upper bound on the size of G in terms of its order, diameter and vertex-connectivity. The result is a strengthening of an old classical theorem of Ore [5] if vertex-connectivity is prescribed and constant.