Average distance, minimum degree, and size - Dankelmann, Peter (Utilitas Mathematica, 2006)
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)2(n + 2√2q - δn)) / ((δ + 1)n2)+O(1), for n, q large and δ constant. Our bound is shown to be best possible.