Weak convexity in graphs

66 Views Asked by At

As we know, a finite undirected graph induces a metric space on the set $V$ of its vertices. A convex set of vertices is defined as a set $S \subseteq V$ such that for any $u,v \in S$, all shortest paths (or geodesics) joining $u$ and $v$ are contained in $S$. Now I wonder if anybody has studied a relaxation of this definition, that requires that at least one shortest path joining $u$ and $v$ be contained in $S$. In Euclidean space both definitions are obviously equivalent, since for every pair of points $x,y$ there is a unique geodesic joining them. Are there other metric spaces, besides graphs, where two points may be joined by more than one geodesic?