×

A characterization of 3-Steiner distance hereditary graphs. (English) Zbl 0888.90140

Summary: Let \(G\) be a connected graph and \(S\subseteq 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\geq 2\), if for every \(S\subseteq 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.

MSC:

90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI