Using minimum degree to bound average distance
Mathematics and Computer Science
We show the average distance mu of a connected graph with n vertices, e edges and minimum degree d satisfies [(n+1)n(n-1)-2e/d+1]/n(n-1) This improves conjectures of the computer program Graffti (Fajtlowicz, Written on the wall, Conjectures made by program Graffiti, University of Houston, 1990), and He and Li (Math. Appl. 4 (1991) 28-34) and the results of Kouider and Winkler (J. Graph Theory 25 (1997) 95 -99). The bound is sharp since complete graphs yield equality.
Beezer, R.A, J.E Riegsecker, and B.A Smith. "Using Minimum Degree to Bound Average Distance." Discrete Mathematics. 226 (2001): 365-371. Print.