neighbourhood

Neighbourhood of a vertex

The neighbourhood $N_i$ of a vertex $v_i$ in a graph is defined as its immediately connected neighbours:

$$N_i=\{v_j:e_{ij}\in E\vee e_{ji}\in E\}$$

Read: ”The neighbourhood $N_i$ of vertex $v_i$ is the set of all vertices $v_j$, such that there is an edge $e_{ij}$ from $v_i$ to $v_j$ in the set of edges $E$ or there is an edge $e_{ji}$ from $v_j$ to $v_i$ in the set of edges $E$.” (for undirected graphs, $e_{ij}=e_{ji}$)
Sometimes this is denoted as $\Gamma (v)$.
The number of verticies in the neighbourhood is called the degree.

When $v_i$ itself is not part of the neighbourhod, we call it the open neighbourhood (default). If it is, then we call it the closed neighbourhood, denoted by $N_G[v]$ (as opposed to $N_G(v)$).

adjacency matrix representation

For undirected graphs:

$$N_i=\{v_j:A_{ij}=1\}$$

For directed graphs:
The out-neighborhood:

$$N_i^{+}=\{v_j:A_{ij}=1\}$$

The in-neighbourhood:

$$N_i^{-}=\{v_j:A_{ji}=1\}$$