Generalized eccentricity, radius, and diameter in graphs

For a vertex v and a (k - 1)-element subset P of vertices of a graph, one c an 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 di stances, one can define the k-eccentricity of the vertex v as the maximum d istance over all P and the k-eccentricity of the set P as the maximum dista nce over all v. If k = 2, one is back with the normal eccentricity. We stud y here the properties of these eccentricity measures, especially bounds on the associated radius (minimum k-eccentricity) and diameter (maximum k-ecce ntricity). (C) 1999 John Wiley & Sons, Inc.