×

Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs. (English) Zbl 1156.05017

In a connected graph \(G=(V,E)\), a set \(S\subset V\) is a (Steiner) geodetic set if all \(v\in V\) lie on some shortest path between two vertices in \(S\) (resp. some Steiner subtree for \(S\) in \(G\)). The minimum cardinality of a (Steiner) geodetic set is the (Steiner) geodetic number \(g(G)\) (resp. \(sg(G)\)). \(G\) is 3-Steiner distance hereditary (3-SDH) if for every 3-vertex set \(S\subset V\) the size of a Steiner subtree for \(S\) is independent from the induced subgraph it is calculated in. \(G\) is HHD-free (house-hole-domino-free) if every cycle of length at least 5 contains at least two chords. A contour vertex of \(G\) maximizes the largest of the distances to all \(v\in V\) over all its neighbours.
It is shown that the contour vertices of any 3-SDH or HHD-free graph form a geodetic set. For 3-SDH graphs it is proven that \(g(G)\leq sg(G)\), and an efficient algorithm is described to determine Steiner intervals, i.e. the union of all Steiner subtrees for a given \(S\) in \(G\).

MSC:

05C12 Distance in graphs
PDFBibTeX XMLCite
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] Bandelt, H.-J.; Mulder, H. M., Three interval conditions for graphs, in: Twelfth British Combinatorial Conference, Norwich, 1989, Ars Combin., 29B, 213-223 (1990)
[4] Bilbao, J. M.; Edelman, P. H., The Shapley value on convex geometries, Discrete Appl. Math., 103, 33-40 (2000) · Zbl 0955.91002
[5] A. Brandstädt, V.B. Le, J.P. Spinrad, Graph Classes: A Survey, SIAM Monograph on Discrete Mathematics and Applications, Philidelphia, 1999.; A. Brandstädt, V.B. Le, J.P. Spinrad, Graph Classes: A Survey, SIAM Monograph on Discrete Mathematics and Applications, Philidelphia, 1999.
[6] Chartrand, G.; Lesniak, L., Graphs and Digraphs (1996), Chapman & Hall: Chapman & Hall New York · Zbl 0890.05001
[7] Chartrand, G.; Harary, F.; Zhang, P., Geodetic sets in graphs, Discuss. Math. Graph Theory, 20, 29-138 (2000) · Zbl 0958.05044
[8] Cáceres, J.; Marquez, A.; Oellermann, O. R.; Puertas, M. L., Rebuilding convex sets in graphs, Discrete Math., 297, 26-37 (2005) · Zbl 1070.05035
[9] J. Cáceres, C. Hernando, M. Mora, M. Pelayo, M.L. Puertas, C. Seara, Geodeticity of the contour of chordal graphs, Discrete Appl. Math. in press, doi:10.1016/j.dam.2007.05.049.; J. Cáceres, C. Hernando, M. Mora, M. Pelayo, M.L. Puertas, C. Seara, Geodeticity of the contour of chordal graphs, Discrete Appl. Math. in press, doi:10.1016/j.dam.2007.05.049. · Zbl 1138.05031
[10] Day, D. P.; Oellermann, O. R.; Swart, H. C., Steiner distance-hereditary graphs, SIAM J. Discrete Math., 7, 437-442 (1994) · Zbl 0805.05021
[11] Day, D. P.; Oellermann, O. R.; Swart, H. C., A characterization of 3-steiner distance hereditary graphs, Networks, 30, 243-253 (1997) · Zbl 0888.90140
[12] Farber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, SIAM J. Algebraic Discrete Methods, 7, 433-444 (1986) · Zbl 0591.05056
[13] Goddard, W., A note on Steiner-distance-hereditary graphs, J. Combin. Math. Combin. Comput., 40, 167-170 (2002) · Zbl 0990.05039
[14] Hammer, P. L.; Maffray, F., Completely separable graphs, Discrete Appl. Math., 27, 85-100 (1990) · Zbl 0694.05060
[15] Howorka, E., A characterization of distance hereditary graphs, Quart. J. Math. Oxford, 28, 417-420 (1977) · Zbl 0376.05040
[16] Howorka, E., A characterization of ptolemaic graphs, J. Graph Theory, 5, 323-331 (1981) · Zbl 0437.05046
[17] Mulder, H. M., The interval function of a graph, Mathematical Centre Tracts, vol. 132 (1980), Mathematisch Centrum: Mathematisch Centrum Amsterdam · Zbl 0446.05039
[18] Nebeský, L., Characterizing the interval function of a connected graph, Math. Bohemica, 123, 137-144 (1998) · Zbl 0937.05036
[19] Oellermann, O. R.; Puertas, M. L., Steiner intervals and Steiner geodetic numbers in distance hereditary graphs, Discrete Math., 307, 88-96 (2007) · Zbl 1113.05030
[20] Van de Vel, M. J.L., Theory of Convex Structures (1993), North-Holland: North-Holland Amsterdam · Zbl 0785.52001
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.