Oellermann, Ortrud R.; Puertas, María Luz Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs. (English) Zbl 1113.05030 Discrete Math. 307, No. 1, 88-96 (2007). 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 E. Kubicka et al., Discrete Appl. Math. 81, 181–190 (1998; Zbl 0898.05044)]. The authors show that for distance-hereditary graphs [see 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. Reviewer: Ján Plesník (Bratislava) Cited in 14 Documents MSC: 05C12 Distance in graphs 05C05 Trees 05C38 Paths and cycles 52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) Citations:Zbl 0898.05044; Zbl 0376.05040 PDFBibTeX XMLCite \textit{O. R. Oellermann} and \textit{M. L. Puertas}, Discrete Math. 307, No. 1, 88--96 (2007; Zbl 1113.05030) Full Text: DOI References: [1] Atici, M., Computational complexity of geodetic set, Internat. J. Comput. Math., 79, 587-591 (2002) · Zbl 0999.05027 [2] Bandelt, H.-J.; Mulder, H. M., Distance-hereditary graphs, J. Combin. Theory Ser. B, 41, 182-208 (1986) · Zbl 0605.05024 [3] Broersma, H. J.; Dahlhaus, E.; Kloks, T., A linear time algorithm for minimum fill-in and tree width for distance-hereditary graphs, Discrete Appl. Math., 99, 367-400 (2000) · Zbl 0940.05064 [4] Cáceres, J.; Márquez, A.; Oellermann, O. R.; Puertas, M. L., Rebuilding convex sets in graphs, Discrete Math., 297, 26-37 (2005) · Zbl 1070.05035 [5] Chartrand, G.; Lesniak, L., Graphs and Digraphs (1996), Chapman & Hall: Chapman & Hall New York · Zbl 0890.05001 [6] Chartrand, G.; Zhang, P., The Steiner number of a graph, Discrete Math., 242, 41-54 (2002) · Zbl 0988.05034 [7] D’Atri, A.; Moscarini, M., Distance-hereditary graphs, Steiner trees and connected domination, SIAM J. Comput., 17, 521-538 (1988) · Zbl 0647.05048 [8] Day, D. P.; Oellermann, O. R.; Swart, H. C., Steiner distance-hereditary graphs, SIAM J. Discrete Math., 7, 437-442 (1994) · Zbl 0805.05021 [9] Faber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, SIAM J. Algebraic Discrete Methods, 7, 433-444 (1986) · Zbl 0591.05056 [10] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman: W.H. Freeman New York · Zbl 0411.68039 [11] Hammer, P. L.; Maffray, F., Completely separable graphs, Discrete Appl. Math., 27, 85-100 (1990) · Zbl 0694.05060 [12] Howorka, E., A characterization of distance-hereditary graphs, Quart. J. Math. Oxford, 28, 417-420 (1977) · Zbl 0376.05040 [13] Kubicka, E.; Kubicki, G.; Oellermann, O. R., Steiner intervals in graphs, Discrete Math., 81, 181-190 (1998) · Zbl 0898.05044 [14] Negami, S.; Xu, G. H., Locally geodesic cycles in 2-self-centered graphs, Discrete Math., 58, 3, 263-268 (1986) · Zbl 0589.05045 [15] Oellermann, O. R.; Tian, S., 24. Steiner centers in graphs, J. Graph Theory, 14, 585-597 (1990) · Zbl 0721.05035 [16] Pelayo, I., Comment on “The Steiner number of a graph” by G. Chartrand and P. Zhang [Discrete Mathematics 242 (2002) 41-54], Discrete Math., 280, 259-263 (2004) · Zbl 1041.05025 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.