Mean distance and minimum degree

Abstract

We prove that in a graph of order n and minimum degree d, the mean distance μ must satisfy . This asymptotically confirms, and improves, a conjecture of the computer program GRAFFITI. The result is close to optimal; examples show that for any d, μ may be larger than n/(d + 1). © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 95–99, 1997