From steiner centers to steiner medians

The Steiner distance of 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 ≥ 2, the Steiner n ‐eccentricity e n ( v ) of a vertex v of a graph G is the maximum Steiner distance among all sets 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 ‐eccentricity. The Steiner n ‐distance of a vertex v of G is defined as. 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 ‐centre and Steiner n ‐median of a tree can be arbitrarily large. Centrality measures that allow every vertex on a shortest path from the Steiner n ‐center to the Steiner n ‐median of a tree to belong to the “center” with respect to one of these measures are introduced and several proeprties of these centrality measures are established. © 1995 John Wiley & Sons, Inc.