THE AVERAGE STEINER DISTANCE OF A GRAPH

The average distance mu(G) of a graph G is the average among the dista nces between all pairs of vertices in G. For n greater than or equal t o 2, the average Steiner n-distance mu(n)(G) of a connected graph G is the average Steiner distance over all sets of n vertices in G. It is shown that for a connected weighted graph G, mu(n)(G) less than or equ al to mu(k)(G) + mu(n+1-k)(G) where 2 less than or equal to k less tha n or equal to n - 1. The range for the average Steiner n-distance of a connected graph G in terms of n and \V(G)\ is established. Moreover, for a tree T and integer k, 2 less than or equal to k less than or equ al to n - 1, it is shown that mu(n)(T) less than or equal to (n/k)mu(k )(T) and the range for mu(n),(T) in terms of n and \(T)\ is establishe d. Two efficient algorithms for finding the average Steiner n-distance of a tree are outlined. (C) 1996 John Wiley & Sons, Inc.