Average distance, minimum degree, and size

Abstract

We give an upper bound on the average distance of a. connected graph of given order, size, diameter, and minimum degree. As a corollary we show that the average distance of a connected graph of order n, size q and minimum degree δ ≥ 2 is at most ((n - √2q - ≥n)²(n + 2√2q - δn)) / ((δ + 1)n²)+O(1), for n, q large and δ constant. Our bound is shown to be best possible.