×

Separation properties of 3-Steiner and 3-monophonic convexity in graphs. (English) Zbl 1252.05045

Summary: Let \(V\) be a finite set and \(\mathcal C\) a collection of subsets of \(V\). The ordered pair \((V,\mathcal C)\) is an alignment if \(\mathcal C\) is closed under taking intersections and contains both \(\emptyset\) and \(V\). If \((V,\mathcal C)\) is an alignment, then \(\mathcal C\) is a convexity for \(V\), and the elements of \(\mathcal C\) are referred to as the convex sets of the convexity \(\mathcal C\). A convex set \(A\) is a half-space if \(V - A\) is convex. The following separation properties have been defined for a given convexity \(\mathcal C\) of \(V\).
{\((S_{1})\)}
For every \(x\in V\), the set \(\{x\}\) is convex.
{\((S_{2})\)}
For every pair \(a,b\in V\), there exist complementary half-spaces \(A,B\) such that \(a\in A\) and \(b\in B\).
{\((S_{3})\)}
For every convex set \(A\) and \(b\in V - A\), there exist complementary half-spaces \(A',B'\) in \(\mathcal C\) such that \(A\subseteq A'\) and \(b\in B'\).
{\((S_{4})\)}
For every pair \(A,B\in \mathcal C\) of disjoint convex sets, there exist complementary half-spaces \(A',B'\) in \(\mathcal C\) such that \(A\subseteq A'\) and \(B\subseteq B'\).
All well-known graph convexities satisfy property \(S_{1}\). Properties of graphs satisfying separation properties \(S_{2},S_{3}\), and \(S_{4}\) with respect to the two most well-known graph convexities, namely, the geodesic and monophonic convexities, have been studied. In this paper we establish properties of graphs satisfying separation properties \(S_{2},S_{3}\), and \(S_{4}\) relative to the 3-Steiner convexity and the 3-monophonic convexity of a graph.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C05 Trees
52A99 General convexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bandelt, H.-J., Graphs with intrinsic \(S_3\) convexities, J. Graph Theory, 13, 215-228 (1989)
[2] Cáceres, J.; Oellermann, O. R., On 3-Steiner simplicial orderings, Discrete Math., 309, 5828-5833 (2009) · Zbl 1221.05042
[3] J. Cáceres, O.R. Oellermann, M.L. Puertas, Minimal trees and monophonic convexity, Discuss. Math. Graph Theory (in press).; J. Cáceres, O.R. Oellermann, M.L. Puertas, Minimal trees and monophonic convexity, Discuss. Math. Graph Theory (in press). · Zbl 1293.05314
[4] 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
[5] Farber, M.; Jamison, R. E., Convexity in graphs and hypergraphs, SIAM J. Algebr. Discrete Methods, 7, 433-444 (1986) · Zbl 0591.05056
[6] Kubicka, E.; Kubicki, G.; Oellermann, O. R., Steiner intervals in graphs, Discrete Appl. Math., 81, 181-190 (1998) · Zbl 0898.05044
[7] Nielsen, M. H.; Oellermann, O. R., Steiner trees and convex geometries, SIAM J. Discrete Math., 23, 680-693 (2009) · 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.