Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Currently I'm dealing with a graph problem but I don't understand one specific notation. What does the following mean:

$$N/(N_{r}\bigcup N_{v})$$

$N$, $N_{r}$, $N_{v}$ are sets of nodes. $N$ is the full set, and the other two are subsets. I understand the notation when it's written with \, but I don't know the meaning of /.

share|improve this question
There are two possibilities. (1) It refers to some kind of quotient structure in which the nodes in $N_r\cup N_v$ are collapsed to a single node. (2) It’s a specifically graph-theoretic notation of some kind. Can you give more context? –  Brian M. Scott Jan 22 '13 at 19:27
Another possibility is that you guessed right and the author was using $/$ as a nonstandard replacement for what we'd write as $-$ or \. That's believable from the context, at least. –  Rick Decker Jan 22 '13 at 19:30
Hi, no Rick, I'm pretty sure the author knew what he was doing. So I can rule that out. Brian, unfortunately I can't upload the paper, because a paid account is needed to download it. However, I asked a professor today, but I didn't really understand what he meant. He said something about modulo. But I don't know what else you want to know. The problem is called p-cable-trench-problem and the author is Marianov. –  user59266 Jan 22 '13 at 19:45
I had a very quick look at the paper, but could not decode it. But there is an email address there, write to the author. –  Chris Godsil Jan 22 '13 at 20:14
Can you make the title more specific? –  Rahul Jan 23 '13 at 20:55

2 Answers 2

The paper can be found here. Looking at the text near Proposition 3 it seems as in Brian's guess is correct: for the node sets $N_r, N_v$ of the directed trees rooted at $r, v$ respectively, $N/(N_r\cup N_v)$ seems to denote just what Brian guessed, the set of nodes in the digraph induced by $N$ where the nodes in the subtrees $N_r, N_v$ are collapsed to a single node.

To see how this "collapse" works (at least as I interpret what Marianov intends), consider this picture:

enter image description here

In the left hand picture I've drawn a directed graph with nodes $N$ consisting of $p, q, r, w, v$ and the three unlabeled nodes at the bottom. As in the article, the tree rooted at $r$ and the tree rooted at $v$ consist of nodes $N_r, N_v$ respectively, so there are three nodes in the set $N_r$ and two in the set $N_v$. If we move those five nodes and superimpose them into one, keeping all of the other edges, we get the picture on the right, where $r, v$, and the three other tree nodes have all been collapsed into one node. In other words, as I interpret things, the four nodes in the right-hand picture are $N/(N_r\cup N_v)$.

share|improve this answer
ok, sorry, but I really don't get it. can you maybe show me that with a small example? what does "collapsed to a single node" mean? How can I picture that. –  user59266 Jan 22 '13 at 22:15
I'll add a picture that might help. –  Rick Decker Jan 23 '13 at 20:39
ok, fair enough, but what's the difference then to N\...? Because in the end, the resulting nodes that I can choose from are the same, isn't it. Thus I wouldn't need this weird notation. –  user59266 Jan 25 '13 at 20:16
As I understand it, if $M, N$ are node sets with $M\subseteq N$, then $N/M$ is the induced graph you get when you collapse all of $M$ to a single node, while N\M would be the induced graph obtained by removing all of $M$. In the example above, we'd wind up with just the isolated nodes $p, q, w$. You should really ask the author. –  Rick Decker Jan 25 '13 at 21:52

Reinhard Diestel’s text Graph Theory uses the notation $G/e$, where $e$ is an edge $\{x,y\}$ of $G$, to denote the graph obtained by ‘contracting the edge $e$ into a new vertex $v_e$, which becomes adjacent to all of the former neighbours of $x$ and $y$’. My best guess is that you’re starting with a graph $G=\langle N,E\rangle$ and contracting all of $N_r\cup N_v$ to a single vertex $v^*$. For $v\in N\setminus(N_r\cup N_v)$ the new graph would have an edge $\{v,v^*\}$ iff there is a $u\in N_r\cup N_v$ such that $\{v,u\}\in E$, i.e., iff there is an edge in $G$ from $v$ to some vertex $u\in N_r\cup N_v$.

share|improve this answer

Your Answer


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.