ON THE STEINER MEDIAN OF A TREE

Let S be a nonempty set of vertices of a connected graph G. Then the S teiner distance of S is the minimum size (number of edges) of a connec ted subgraph of G containing S. Let n greater than or equal to 2 be an integer and suppose that G has at least n vertices. Then the Steiner n-distance of a vertex v of G is defined to be the sum of the Steiner distances of all sets of n vertices that include v. The Steiner n-medi an M(n)(G) of G is the subgraph induced by the vertices of minimum Ste iner n-distance. We show that the Steiner n-median of a tree is connec ted and determine those trees that are Steiner n-medians of trees, and show that if T is a tree with more than n vertices, then M(n)(T) subs et of or equal to M(n+1)(T). Further, a O(\V(T)\) algorithm for findin g the Steiner n-median of a tree T is presented and a O(n \V(T)\(2)) a lgorithm for finding the Steiner n-distances of all vertices in tree T is described. For a connected graph G of order p greater than or equa l to n, the n-median value of G is the least Steiner n-distance of any of its vertices. For p greater than or equal to 2n - 1, sharp upper a nd lower bounds for the n-median values of trees of order p are given, and it is shown that among all trees of a given order, the path has m aximum n-median value.