Neighborhood

In graph theory, the neighborhood ^[1] of a vertex $v$ in a graph $G$ is the edge induced subgraph, i.e. the graph composed of all the vertices adjacent to $v$ and all the edges connecting them.

Definition

---

Definition 1 (Neighbor)

Let $G=(V,E)$ be a graph. A vertex $u\in V$ is a neighbor of a vertex $v\in V$ if $u$ is adjacent to $v$, i.e. if $\{u,v\}\in E$.

Definition 2 (Open neighborhood)

Let $G=(V,E)$ be a graph and $v\in V$ a vertex. The open neighborhood of $v$ is the edge induced subgraph on the set of neighbors of $v$, excluding $v$ itself.

Definition 3 (Closed neighborhood)

Let $G=(V,E)$ be a graph and $v\in V$ a vertex. The closed neighborhood of $v$ is the edge induced subgraph on the set of neighbors of $v$, including $v$ itself.

Notation

---

The open neighborhood of $v$ is denoted $N_G(v)$, or simply $N(v)$ when the graph is unambiguous, and the closed neighborhood is denoted $N_G[v]$. The same neighborhood notation may also be used to refer to the set of adjacent vertices rather than the corresponding induced subgraph.

Directed graphs

---

In a directed graph, the neighborhood of a vertex $v$ splits into two directed notions: the in-neighborhood $N^{-}(v)$, the set of neighbors $u$ with a directed edge $(u,v)$, and the out-neighborhood $N^{+}(v)$, the set of neighbors $u$ with a directed edge $(v,u)$.

References

1. [1]

   “Neighbourhood (graph theory)”, Wikipedia, Available: https://en.wikipedia.org/wiki/Neighbourhood_(graph_theory), Accessed: 2026-07-31 ↩