Cut Locus in a Graph - MathOverflow

Cut Locus in a Graph

2011-03-11T23:51:03Z

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:

I see two possible interpretations of the phrase "distinct shortest paths":

Two paths are distinct if they are not identical.
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!

Answer by Gjergji Zaimi for Cut Locus in a Graph

2011-03-12T03:35:28Z

I cannot comment on the first question of whether this concept has been studied, but it sounds quite interesting. This is more of a comment of course, here are a couple of first observations.

The cut locus is a disjoint union of cut loci in the blocks of the starting graph (assuming it is not 2-connected). So the question about which graphs have cut loci which are forests can be reduced to the 2-connected case.

On the other hand, it seems that any graph can appear as the cut locus of a graph. This is true for the case of Riemann surfaces (See here). And perhaps a way to prove this claim is by discretizing those surfaces. If this works it suggests that the problem is still geometric in nature, and maybe a purely graph theoretical classification of cut loci is not possible (this is just speculation of course, I don't actually have a feel on how hard this problem is).

Answer by Anonymous for Cut Locus in a Graph

2011-03-12T15:02:49Z

Hopefully, I didn't completely misread the definitions. So here goes.

If we use definition 1. of distinct, (b) could be simplified to "all edges between vertices at the same distance from x" (and the vertices these edge induce). Indeed, since the endpoints are different, the paths are distinct in the sense 1.

To determine if $C(x)$ contains cycles, we do not need to look at (a) (it only contains vertices, but no edges). Thus, with definition 1., it boils down to determining if the graph induced by vertices at distance $i$ from $x$ contains a cycle for each $i$.

This seems make the question slightly "less interesting" since we can add a universal vertex $x$ to any graph $G$ (to make $G$ the cut locus of $x$). We could also subdivide the edge incident to $x$ in $G+x$ to make $G$ appear in the cut locus at higher distances.

In fact, for definition 1., any question about the cut locus involving edges would only involve the graph induced by vertices at distance $i$ from $x$ for each value of $i$ (i.e., the $i$th neighbourhood of $x$).

Actually, even for definition 2., we only need to look at (b) for any question involving edges of $C(x)$.

As for definition 2., as Gjergi pointed out, the only vertices that can be in the cut locus are those in the same 2-connected component (block) as $x$. If $x$ is a cut vertex (and thus in multiple blocks), we get a different component of $C(x)$ for each block so we may want to consider them separately anyway. Again, we get different components for vertices at each distance in $C(x)$, so we may as well consider them separately. Let $G_i(x)$ be the graph induced by vertices at distance $i$ from $x$ in $C(x)$.

Then $G_1(x)$ is the graph induced by all vertices in the block of $x$ at distance 1 from $x$.

$G_2(x)$ is the graph induced by all vertices of $G-E(G_1(x))$ in the block of $x$ at distance 2 from $x$.

$G_3(x)$ is the graph induced by all vertices of $G-E(G_1(x))-E(G_2(x))$ in the block of $x$ at distance 3 from $x$.

and so on.