
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.
Geodetic number, Distance in graphs, Steiner interval, Distance-hereditary graph, Steiner geodetic number, Trees, Theoretical Computer Science, Contour vertices, Steiner geodetic set, Discrete Mathematics and Combinatorics, Paths and cycles, Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
Geodetic number, Distance in graphs, Steiner interval, Distance-hereditary graph, Steiner geodetic number, Trees, Theoretical Computer Science, Contour vertices, Steiner geodetic set, Discrete Mathematics and Combinatorics, Paths and cycles, Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 23 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
