Premium
A characterization of 3‐Steiner distance hereditary graphs
Author(s) -
Day D. P.,
Oellermann Ortrud R.,
Swart Henda C.
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199712)30:4<243::aid-net2>3.0.co;2-j
Subject(s) - combinatorics , mathematics , vertex connectivity , steiner tree problem , graph , connectivity , discrete mathematics , vertex (graph theory)
Let G be a connected graph and S ⊆ V ( G ). Then, the Steiner distance of S in G , denoted by d G ( S ), is the smallest number of edges in a connected subgraph of G that contains S . A connected graph G is k ‐Steiner distance hereditary, k ≥ 2, if for every S ⊆ V ( G ) such that | S | = k and every connected induced subgraph H of G containing S , d H ( S ) = d G ( S ). Some 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. © 1997 John Wiley & Sons, Inc. Networks 30: 243–253, 1997