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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm having some problem with nomenclature some structures and quantities related to weighted directed graph.

Suppose that $A \in \mathbb{R}_+^{N \times N}$ is the weighted adjacency matrix of a weighted directed graph. In this case, when a node $v$ is connected to $w$, then $a_{v,w}$ is a positive real number that indicates how strong is this connection. $a_{v,w}=0$ means that $v$ is not connected toward $w$ (but $w$ can, if $a_{w,v}>0$). In general, $a_{v,w} \neq a_{w,v}$.

I have the following sets: $$\mathcal{N}^+_v = \{w : a_{v,w}>0\}$$ $$\mathcal{N}^-_v = \{w : a_{w,v}>0\}$$ $$\mathcal{N}_v = \{w : a_{w,v}>0 \vee a_{v,w}>0\}$$ How are these set called?

Also, I have the following quantities: $$\delta^+_v = |\mathcal{N}^+_v|$$ $$\delta^-_v = |\mathcal{N}^-_v|$$ $$\delta_v = |\mathcal{N}_v|$$ $$d^+_v = \sum_{w \in \mathcal{N}^+_{v}}a_{v,w} $$ $$d^-_v = \sum_{w \in \mathcal{N}^-_{v}}a_{w,v} $$

Which are the names of the previous quantities?

On books I have found very different words and now I'm a little bit confused about the concept of "neighborhood" and of "degree".

share|cite|improve this question
up vote 3 down vote accepted

First consider unweighted directed graphs. I'd say that your $\mathcal{N}_v^+$ is the set of out-neighbors of $v$ and that your $\mathcal{N}_v^-$ is the set of in-neighbors. Their cardinalities are the in-degree and out-degree respectively. (Or in- and out-valency.) But if in a paper I came across $\mathcal{N}_v^+$, I would not know if it referred to in-neighbors or out-neighbors.

If I came across $\mathcal{N}_v$, I'd usually read it as the set of vertices joined by an arc to $v$, but I'd be happier if the author stated this explicitly. Its cardinality is the degree of the directed graph.

For weighted graphs there is no settled system of notation, each author has to explain their terminology.

share|cite|improve this answer
Thank you for your reply! I didn't understand what you mean when you say "But if I came across in a paper $N^+_v$, I would not know if it referred to in-neighbors or out-neighbors." – the_candyman Jun 9 '13 at 10:25
@the_candyman: it's a typo, I've edited my response. – Chris Godsil Jun 9 '13 at 13:31
got it, thanks again! – the_candyman Jun 9 '13 at 13:46

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.