This question asks for an analog of the convex hull in a graph that parallels
(as far as possible) convex sets in Euclidean space.
Let $G$ be a simple, undirected graph, and let $S \subseteq V$ be a subset of its vertices.
Use geodesic as synonymous with shortest path, where distance is measured by
the number of edges in a path.
I would like to define the convex hull $CH(S)$ as the set of vertices of $G$ produced by
the following process. $S$ is in $CH(S)$. For each $x,y \in CH(S)$, all the vertices
along (all) the geodesics between $x$ and $y$ are included in $CH(S)$. Etc.: For every pair of
vertices in $CH(S)$, all the vertices on the geodesics between these pairs are thrown into $CH(S)$, until $CH(S)$
stabilizes.
As an example, consider the graph $G$ depicted below, with $S=\{1,2,9\}$ (left).
What is the convex hull $CH(S)$ of $\{1,2,9\}$? It must include all the vertices
on the geodesics from $1$ to $2$: $(1,7,3,2)$;
and the geodesics from $2$ to $9$: $(2,12,9)$;
and the geodesics from $1$ to $9$: $(1,7,8,9)$ and $(1,6,5,9)$—NB: two of equal length.
So it must include $\{1,2,3,5,6,7,8,9,12\}$ (right).
Now I would like these properties for the convex-hull definition:
(1) Any geodesic in $G$ meets $CH(S)$ in a segment, a single connected path.
For example, the unique geodesic from $1$ to $11$ meets $CH(1,2,9)$ in the
single point $\mathbf{1}$, which is a segment. Another example is the geodesics between
$4$ and $14$: $(14,13,\mathbf{12,9,8},10,11,4)$ or $(14,13,\mathbf{12,9,5,6,1},4)$.
I believe this holds; I could sketch a proof…
(2) $CH(S)$ can be viewed as the intersection of the halfspaces determining the
boundary of $CH(S)$.
Here I am having difficulty coming up with a definition of halfspace that makes sense in this context, and shows that $CH(S)$ is the intersection of halfspaces.
I want to say something like, "a set of vertices $S$ constitutes a halfspace if both $S$ and its complement in $G$ are convex."
(3) I think the latter uncertainty derives from the uncertainty how to define what
should serve as an extreme point of $CH(S)$. Is there a natural definition?
I sense that I am reinventing a wheel turned over and over by many researchers before me.
If that is the case, pointers would be welcomed! Thanks!
Best Answer
One particular class of graphs where this notion of convexity is used is that of median graphs. In this context one can make sense of halfspaces as you described and even carry over some analogs of certain theorems about convex sets, such as Helly's theorem. This isn't far from Kevin's comment because such graphs are retracts of hypercubes.
There is quite a bit of literature on convexity for graphs. One can basically ask to translate any classical convexity result to this new setting. Suppose for example you consider a vertex $v\in S$ to be an extreme point of the convex set $S\subset G$, if $S/\lbrace v\rbrace$ is also convex. Then the class of graphs for which every convex set is the convex hull of its extreme points is precisely the class of chordal graphs without induced $3$-fans. This was proved in "Convexity in graphs and hypergraphs" by M. Farber, R.E. Jamison (SIAM J. Algebraic Discrete Math., 7 (1986), pp. 433–444). This paper will probably also provide a good starting point for exploring the literature.