Steiner centers and Steiner medians of graphs

Let G be a connected graph and S a set of vertices of G. The Steiner distance of S is the smallest number of edges in a connected subgraph of G that contains S   and is denoted by dG(S)dG(S) or d(S)d(S). The Steiner n  -eccentricity en(v)en(v) and Steiner n  -distance dn(v)dn(v) of a vertex vv in G   are defined as en(v)=max{d(S)|en(v)=max{d(S)|S⊆V(G)S⊆V(G), |S|=n|S|=n and v∈S}v∈S} and dn(v)=∑{d(S)|dn(v)=∑{d(S)|S⊆V(G)S⊆V(G), |S|=n|S|=n and v∈S}v∈S}, respectively. The Steiner n  -center Cn(G)Cn(G) of G is the subgraph induced by the vertices of minimum n-eccentricity. The Steiner n  -median Mn(G)Mn(G) of G is the subgraph induced by those vertices with minimum Steiner n-distance. Let T   be a tree. Oellermann and Tian [O.R. Oellermann, S. Tian, Steiner centers in graphs, J. Graph Theory 14 (1990) 585–597] showed that Cn(T)Cn(T) is contained in Cn+1(T)Cn+1(T) for all n⩾2n⩾2. Beineke et al. [L.W. Beineke, O.R. Oellermann, R.E. Pippert, On the Steiner median of a tree, Discrete Appl. Math. 68 (1996) 249–258] showed that Mn(T)Mn(T) is contained in Mn+1(T)Mn+1(T) for all n⩾2n⩾2. Then, Oellermann [O.R. Oellermann, On Steiner centers and Steiner medians of graphs, Networks 34 (1999) 258–263] asked whether these containment relationships hold for general graphs. In this note we show that for every n⩾2n⩾2 there is an infinite family of block graphs G   for which Cn(G)⊈Cn+1(G)Cn(G)⊈Cn+1(G). We also show that for each n⩾2n⩾2 there is a distance–hereditary graph G   such that Mn(G)⊈Mn+1(G)Mn(G)⊈Mn+1(G). Despite these negative examples, we prove that if G   is a block graph then Mn(G)Mn(G) is contained in Mn+1(G)Mn+1(G) for all n⩾2n⩾2. Further, a linear time algorithm for finding the Steiner n-median of a block graph is presented and an efficient algorithm for finding the Steiner n-distances of all vertices in a block graph is described.