Generalized Eccentricity, Radius, and Diameter in Graphs

For a vertex v and a (k - 1)-element subset P of vertices of a graph, one can define the distance from v to P in various ways, including the minimum, average, and maximum distance from v to P. Associated with each of these distances, one can define the k-eccentricity of the vertex v as the maximum distance over all P and the k-eccentricity of the set P as the maximum distance over all v. If k = 2, one is back with the normal eccentricity. We study here the properties of these eccentricity measures, especially bounds on the associated radius (minimum k-eccentricity) and diameter (maximum k-eccentricity). © 1999 John Wiley & Sons, Inc. Networks 34: 312-319, 1999