Neighbourhood (graph theory)

In graph theory, an adjacent vertex of a vertex v in a graph is a vertex that is connected to v by an edge. The neighbourhood of a vertex v in a graph G is the subgraph of G induced by all the vertices adjacent to v, i.e., the graph composed of all the vertices adjacent to v and all the edges connecting them.

The neighbourhood is often denoted by ⁠${\displaystyle N_{G}(v)}$⁠ or (when the graph is unambiguous) ⁠${\displaystyle N(v)}$⁠. The same neighbourhood notation may also be used to refer to the set of adjacent vertices rather than the corresponding induced subgraph. The neighbourhood described above does not include v itself, and is more specifically the open neighbourhood of v; it is also possible to define a neighbourhood in which v itself is included, called the closed neighbourhood of v and denoted by ⁠${\displaystyle N_{G}[v]}$⁠. When stated without any qualification, a neighbourhood is assumed to be open.

Neighbourhoods may be used to represent graphs in computer algorithms, via the adjacency list and adjacency matrix representations. Neighbourhoods are also used in the clustering coefficient of a graph, which is a measure of the average density of its neighbourhoods. In addition, many important classes of graphs may be defined by properties of their neighbourhoods, or by symmetries that relate neighbourhoods to each other.

An isolated vertex has no adjacent vertex. The degree of a vertex v is the number of vertices adjacent to v. A special case is a loop, i.e., an edge that connects a vertex to itself; if such an edge exists, then the vertex belongs to its own neighbourhood.