Neighbourhood (graph theory)

The neighbourhood of a vertex v in a graph G is the subgraph of G induced by all vertices adjacent to v, i.e., the graph composed of the vertices adjacent to v and all edges connecting vertices adjacent to v. The neighbourhood is often denoted ⁠

The same neighbourhood notation may also be used to refer to sets of adjacent vertices rather than the corresponding induced subgraphs.

When stated without any qualification, a neighbourhood is assumed to be open.

The degree of a vertex is equal to the number of adjacent vertices.

If all vertices in G have neighbourhoods that are isomorphic to the same graph H, G is said to be locally H, and if all vertices in G have neighbourhoods that belong to some graph family F, G is said to be locally F.[1] For instance, in the octahedron graph, shown in the figure, each vertex has a neighbourhood isomorphic to a cycle of four vertices, so the octahedron is locally C4.

In this graph, the vertices adjacent to 5 are 1, 2 and 4. The neighbourhood of 5 is the graph consisting of the vertices 1, 2, 4 and the edge connecting 1 and 2.
In the octahedron graph , the neighbourhood of any vertex is a 4- cycle .