Separation properties for 3-Steiner and 3-Monophonic convexity in graphs
Presented by Dr. Ortrud OELLERMANN
Type: Oral presentation
Track: Metric Graph Theory
A convex set $X$ in a graph with vertex set $V$ is a half-space if $V-X$ is also convex. A convexity has separation property (i) $(S_2)$ if every pair of vertices belong to complementary half-spaces; (ii) $(S_3)$ if for every convex set $A\subset V(G)$ and $b\in V(G)-A$, there exist complementary half-spaces $A'$ and $B'$ such that $A\subseteq A'$ and $b\in B'$; (iii) $(S_4)$ if for every pair $A,B\subseteq V(G)$ of disjoint convex sets, there exist complementary half-spaces $A',B'$ in $G$ such that $A\subseteq A'$ and $B\subseteq B'$. In this talk we consider the above separation properties with respect to two new graph convexities and characterize those graphs for which the corresponding convexities satisfy properties $(S_3)$ and $(S_4)$. We also present some observations on the $(S_2)$ property.