FROM STEINER CENTERS TO STEINER MEDIANS

The Steiner distance of a set S of vertices in a connected graph G is the minimum number of edges in a connected subgraph of G containing S. For n greater than or equal to 2, the Steiner n-eccentricity e(n)(v) of a vertex v of a graph G is the maximum Steiner distance among all s ets S of n vertices of G that contain v. The Steiner n-center of G is the subgraph induced by those vertices of G having minimum n-eccentric ity. The Steiner n-distance of a vertex v of G is defined as d(G)((n)) (v) = Sigma{d(S)\S subset of or equal to V(G), v is an element of S an d \S\ = n}. The Steiner n-median of G is the subgraph of G induced by the vertices of G of minimum Steiner n-distance. Known algorithms for finding the Steiner n-centers and Steiner n-medians of trees are used to show that the distance between the Steiner n-center and Steiner n-m edian of a tree can be arbitrarily large. Centrality measures that all ow every vertex on a shortest path from the Steiner n-center to the St einer n-median of a tree to belong to the ''center'' with respect to o ne of these measures are introduced and several properties of these ce ntrality measures are established. (C) 1995 John Wiley & Sons, Inc.