# Understanding the notation $N/(N_{r}\bigcup N_{v})$ in graph theory

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

-
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

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:

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

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

-