ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 MS Classification: 05C12 Swart, Henda C., University of Natal, Durban, South Africa Generalised Measures of Distance 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 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 measures, together with those of Steiner distance, especially bounds on the associated radius (minimum k-eccentricity) and diameter (maximum k-eccentricity).