Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs (Q861797): Difference between revisions

The closure of a set \(S\) of vertices in a connected graph \(G\) is \(\bigcup_{u,v\in S}I[u,v]\) where the interval \(I[u,v]\) is the union of all vertices that belong to some shortest \(u\)-\(v\) path. If the closure is \(V(G)\), then \(S\) is called a geodetic set. The geodetic number of \(G\), denoted by \(g(G)\), is the smallest cardinality of a geodetic set in \(G\). If instead shortest paths Steiner trees for \(S\) are considered, one gets the Steiner interval of \(S\) and the Steiner geodetic number of \(G\) [see \textit{E. Kubicka} et al., Discrete Appl. Math. 81, 181--190 (1998; Zbl 0898.05044)]. The authors show that for distance-hereditary graphs [see \textit{E. Howorka}, Q. J. Math., Oxf. II. Ser. 28, 417--420 (1977; Zbl 0376.05040)] \(g(G)\leq sg(G)\), but that \(g(G)/sg(G)\) can be arbitrarily large if \(G\) is not distance-hereditary. An efficient algorithm is developed for finding the Steiner intervals and Steiner geodetic numbers of distance-hereditary graphs.