×

Local Steiner convexity. (English) Zbl 1205.05191

Summary: Let \(G\) be a connected graph and let \(S\) be a set of vertices in \(G\). The Steiner distance \(d(S)\) of \(S\) is the minimum size of a subtree of \(G\) containing \(S\). Such a subtree of size \(d(S)\) is a Steiner tree for \(S\). The set \(S\) is \(g\)-convex if it contains the set of all vertices that lie on some shortest \(u-v\) path in \(G\) for every pair \(u\) and \(v\)of vertices in \(S\). The set \(S\) is \(k\)-Steiner convex, denoted by \(g\)k-convex, if for every \(k\)-element subset \(R\) of \(S\), every vertex that belongs to some Steiner tree for \(R\) is also in \(S\). Thus, \(S\) is \(g_{2}\)-convex if and only if it is \(g\)-convex. In this paper, we distinguish three local convexity notions for \(g_{3}\)-convexity and we characterize the graphs for which two of these conditions hold. For the third condition we determine some necessary conditions and some sufficient conditions for the graph class satisfying this condition.

MSC:

05C75 Structural characterization of families of graphs
05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Cáceres, O.R. Oellermann, On 3-Steiner simplicial orderings, Discrete Math. (2008), in press (doi:10.1016/j.disc.2008.05.047; J. Cáceres, O.R. Oellermann, On 3-Steiner simplicial orderings, Discrete Math. (2008), in press (doi:10.1016/j.disc.2008.05.047 · Zbl 1221.05042
[2] Chartrand, G.; Oellermann, O. R.; Tian, S. L.; Zou, H. B., Steiner distance in graphs, Časopis Pěst. Mat., 114, 4, 399-410 (1989) · Zbl 0688.05040
[3] Dragan, F. F.; Nicolai, F.; Brandstädt, A., Convexity and HHD-free graphs, SIAM J. Discrete Math., 12, 119-135 (1999) · Zbl 0916.05060
[4] Farber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, SIAM J. Algebr Discrete Methods, 7, 433-444 (1986) · Zbl 0591.05056
[5] Farber, M.; Jamison, R. E., On local convexity in graphs, Discrete Math., 66, 231-247 (1987) · Zbl 0619.05032
[6] Kubicka, E.; Kubicki, G.; Oellermann, O. R., Steiner intervals in graphs, Discrete Appl. Math., 81, 181-190 (1998) · Zbl 0898.05044
[7] M.H. Nielsen, O.R. Oellermann, Steiner trees and convex geometries (submitted for publication); M.H. Nielsen, O.R. Oellermann, Steiner trees and convex geometries (submitted for publication) · Zbl 1191.05037
[8] 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
[9] 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.