Neighborhood

Link

This note lacks links.

In graph theory, the neighborhood ^[1] of a vertex $v$ in a graph $G$ is the edge induced subgraph on the set of vertices adjacent to $v$ .

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,v\}\in E$$

that is, if $u$ and $v$ are ??adjacent??, joined by an edge of $G$.

Definition 2 (Open neighborhood)

Let $G=(V,E)$ be a graph and $v\in V$ a vertex. The open neighborhood of $v$ is

$$N(v):=\{u\in V:u\ne v\wedge \{u,v\}\in E\}$$

the set of vertices other than $v$ that are ??adjacent?? to $v$.

Definition 3 (Closed neighborhood)

Let $G=(V,E)$ be a graph and $v\in V$ a vertex. The closed neighborhood of $v$ is

$$N[v]:=\{v\}\cup \{u\in V:u\ne v\wedge \{u,v\}\in E\}$$

the set of vertices that arr ??adjacent?? to $v$ including $v$ itself.

The neighborhood of $v$ can also be formulated as an ??edge induced subgraph??. Let $F:=\{\{u,v\}\in E:u\in V\}$ be the set of edges ??incident?? to $v$. The edge induced subgraph $G[F]$ has vertex set $N[v]$, since $v$ and every neighbor of $v$ appear as endpoints of some edge in $F$, and its edge set is $F$ 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 ↩