Average Distance in Graphs

Dr. Peter Dankelmann

University of Natal
Durban, South Africa

January 16, 1998

Abstract

The average distance of a connected graph G is the average of the distances between all pairs of vertices in G. If G represents a transportation network joining facilities, then the average distance is essentially the expected transportation time between two randomly chosen facilities. We present a survey of results on the average distance and discuss related algorithmic problems. Moreover, we consider generalizations and variations of the average distance.