Skip to main content
5 of 7
Image link broken; now fixed.
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

Cut Locus in a Graph

I am wondering if the concept of a cut locus has been defined and explored in discrete graphs, rather than their usual home on manifolds?

The Wikipedia definition (which I believe I (co-?)authored) is:

The cut locus of $S$ is the closure of the set of all points $p\in X$ that have two or more distinct shortest paths in $X$ from $S$ to $p$.

For my application, $S$ is a single vertex $x$ of a graph $G$, and path length is measured by the number of edges in a path. One possible defintion is:

The cut locus $C(x)$ of a vertex $x$ in a graph $G$ is (a) the set of all the vertices $v$ that have two or more distinct paths from $x$, unioned with (b) all pairs of vertices $(u,v)$—and the edge between them—such that $u$ and $v$ have distinct shortest paths from $x$ of the same length, and $(u,v)$ is an edge of $G$.

This definition is a bit cumbersome, but I want to capture both even (a) and odd (b) cycles. Here is an example, with the even-cycle vertices one color, the odd-cycle edges another:
Cut Locus in Graph
I see two possible interpretations of the phrase "distinct shortest paths":

  1. Two paths are distinct if they are not identical.
  2. Two paths are distinct if they are disjoint, except for the start and end vertices.

The figure above uses the first definition, whereas the second definition would remove the two *-ed vertices from the cut locus (because the paths are not identical; rather they share interior vertices and/or edges and so they are not disjoint).

Again, my main question is: Has this this or similar notions been studied? I am hoping to find theorems in the literature of the form:

If $G$ satisfies properties $\{ ... \}$, then $C(x)$ satisfies properties $\{ ... \}$.

For example, under what conditions on $G$ is the cut locus a forest (i.e., devoid of cycles)? I know this is a fishing expedition, but: Thanks for any pointers or ideas!

Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958