Cut Locus in a Graph - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T00:43:31Z http://mathoverflow.net/feeds/question/58212 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/58212/cut-locus-in-a-graph Cut Locus in a Graph Joseph O'Rourke 2011-03-11T23:51:03Z 2011-03-12T15:02:49Z <p>I am wondering if the concept of a <em>cut locus</em> has been defined and explored in discrete graphs, rather than <a href="http://en.wikipedia.org/wiki/Cut_locus_%2528Riemannian_manifold%2529" rel="nofollow">their usual home on manifolds</a>?</p> <p>The <a href="http://en.wikipedia.org/wiki/Cut_locus" rel="nofollow">Wikipedia definition</a> (which I believe I (co-?)authored) is:</p> <blockquote> <p>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$.</p> </blockquote> <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:</p> <blockquote> <p>The <em>cut locus</em> $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)$&mdash;and the edge between them&mdash;such that $u$ and $v$ have distinct shortest paths from $x$ of the same length, and $(u,v)$ is an edge of $G$.</p> </blockquote> <p>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: <br /><img src="http://cs.smith.edu/~orourke/MathOverflow/GraphCutLocus.jpg" alt="Cut Locus in Graph"><br /> I see two possible interpretations of the phrase "distinct shortest paths":</p> <ol> <li> Two paths are <em>distinct</em> if they are not identical.</li> <li> Two paths are <em>distinct</em> if they are disjoint, except for the start and end vertices.</li> </ol> <p>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).</p> <p>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:</p> <blockquote> <p>If $G$ satisfies properties <code>$\{ ... \}$</code>, then $C(x)$ satisfies properties <code>$\{ ... \}$</code>.</p> </blockquote> <p>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!</p> http://mathoverflow.net/questions/58212/cut-locus-in-a-graph/58228#58228 Answer by Gjergji Zaimi for Cut Locus in a Graph Gjergji Zaimi 2011-03-12T03:35:28Z 2011-03-12T03:35:28Z <p>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.</p> <p>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.</p> <p>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 <a href="http://arxiv.org/abs/1103.1759" rel="nofollow">here</a>). 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).</p> http://mathoverflow.net/questions/58212/cut-locus-in-a-graph/58268#58268 Answer by Anonymous for Cut Locus in a Graph Anonymous 2011-03-12T15:02:49Z 2011-03-12T15:02:49Z <p>Hopefully, I didn't completely misread the definitions. So here goes.</p> <p>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.</p> <p>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$.</p> <p>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.</p> <p>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$).</p> <p>Actually, even for definition 2., we only need to look at (b) for any question involving edges of $C(x)$.</p> <p>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)$.</p> <p>Then $G_1(x)$ is the graph induced by all vertices in the block of $x$ at distance 1 from $x$.</p> <p>$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$.</p> <p>$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$.</p> <p>and so on.</p>