Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
I'm not sure I'm following all of your definition (e.g.: is C(x) a collection of vertices or a collection of vertices and edges?), but have you looked into the notions of 2- or bi-connectivity, particularly the notion of biconnected components? en.wikipedia.org/wiki/Biconnected_component –  mhum Mar 12 '11 at 3:50
    
@mhum: As I defined it, $C(x)$ is a subgraph of $G$, consisting of vertices and edges. But if the graph has no odd cycles, it would only contain vertices, no edges. –  Joseph O'Rourke Mar 12 '11 at 14:49

2 Answers 2

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).

share|improve this answer
1  
Thanks for your interest, Gjergji! I note that the paper to which you link is only two days old! –  Joseph O'Rourke Mar 12 '11 at 3:45

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.

share|improve this answer
    
That $G+x$ renders any $G$ the cut locus w.r.t. $x$ is an astute observation! –  Joseph O'Rourke Mar 13 '11 at 16:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.