STEINER INTERVALS IN GRAPHS

Let G be a graph and u, v two vertices of G. Then the interval from u to v consists of all those vertices that lie on some shortest u-v path . Let S be a set of vertices in a connected graph G. Then the Steiner distance d(G),(S) of S in G is the smallest number of edges in a conne cted subgraph of G that contains S. Such a subgraph is necessarily a t ree called a Steiner tree for S. The Steiner interval I-G,(S) of S con sists of all those vertices that lie on some Steiner tree for S. Let S be an n-set of vertices of G and suppose that k less than or equal to n. Then the k-intersection interval of S, denoted by I-k,(S) is the i ntersection of all Steiner intervals of all k-subsets of S. It is show n that if S = {u(1), u(2),...,u(n)},, is a set of n greater than or eq ual to 2 vertices of a graph G and if the 2-intersection interval of S is nonempty and x is an element of I-2,(S), then d(S) = Sigma(i=1)(n) d(u(i),x). It is observed that the only graphs for which the 2-inters ection intervals of all n-sets, n greater than or equal to, 4, are non empty are stars. Moreover, for every it greater than or equal to 4, th ose graphs with the property that the 3-intersection interval of every n-set is nonempty are completely characterized. In general, if n = 2k , those graphs G for which I-k,(S) is nonempty for every n-set S of G are characterized.