A CHARACTERIZATION OF 3-STEINER DISTANCE HEREDITARY GRAPHS

Let G be a connected graph and S subset of or equal to V(G). Then, the Steiner distance of S in G, denoted by d(G)(S), is the smallest numbe r of edges in a connected subgraph of G that contains S. A connected g raph G is k-Steiner distance hereditary, k greater than or equal to 2, if for every S subset of or equal to V(G) such that \S\ = k and every connected induced subgraph H of G containing S, d(H)(S) = d(G)(S). So me general properties about the cycle structure of k-Steiner distance hereditary graphs are established. These are then used to characterize 3-Steiner distance hereditary graphs. (C) 1997 John Wiley & Sons, Inc .