On Steiner centers and Steiner medians of graphs

Let G be connected graph and S a set of vertices of G. Then a Steiner tree for S is a connected subgraph of G of smallest size (number of edges) that contains S. The size of such a subgraph is called the Steiner distance for S and is denoted by d(S). For a vertex v of G, and integer n, 2 less than o r equal to n less than or equal to \V(G)\, the Steiner n-eccentricity e(n)( v) of v is defined as e(n)(v) = max{d(S)\ S subset of or equal to V(G), \S\ = n, and v is an element of S}. The Steiner n-radius rad(n)G and Steiner n -diameter diam(n)G are defined as the minimum and maximum n-eccentricity re spectively, taken over all vertices of G. Relationships between rad(n)G and diam(n)G are given if G is a tree and a conjecture (with some supporting r esults) is made that relates these parameters for general graphs. The subgr aph induced by these vertices with n-eccentricity rad(n)G is called the Ste iner n-center of G and is denoted by C-n(G). It is shown that every graph i s the Steiner n-center of some graph. The Steiner n-distance of a vertex v, denoted by d(n)(v), is defined by d(n)(v) = Sigma{d(S)\v is an element of S, \S\ = n}. The Steiner n-median M-n(G) of G is the subgraph induced by th ose vertices with minimum Steiner n-distance. Algorithms for finding C-n(T) and M-n(T) for a tree T are described. It is shown that the distance betwe en the C-n(T) and M-n(T) for a tree T can be arbitrarily large. Eccentricit y measures are defined that extend those of the Steiner n-eccentricity and Steiner n-distance of a vertex. Then it is shown that every vertex on a sho rtest path between the Steiner n-center and Steiner n-median of a tree belo ngs to a "center" relative to one of these eccentricity measures. (C) 1999 John Wiley & Sons, Inc.