A CHARACTERIZATION OF 3-STEINER DISTANCE HEREDITARY GRAPHS

Citation
Dp. Day et al., A CHARACTERIZATION OF 3-STEINER DISTANCE HEREDITARY GRAPHS, Networks, 30(4), 1997, pp. 243-253
Citations number
6
Journal title
ISSN journal
00283045
Volume
30
Issue
4
Year of publication
1997
Pages
243 - 253
Database
ISI
SICI code
0028-3045(1997)30:4<243:ACO3DH>2.0.ZU;2-4
Abstract
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 .