From steiner centers to steiner medians

Abstract 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 en(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 magnified image . 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.