graph theory, an adjacent vertex of a
vertexv 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 Ginduced 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 or (when the graph is unambiguous) . The same neighbourhood notation may also be used to refer to sets of adjacent vertices rather than the corresponding induced subgraphs. 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 and denoted by . 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.
isolated vertex has no adjacent vertices. The
degree of a vertex is equal to the number of adjacent vertices. A special case is a
loop that connects a vertex to itself; if such an edge exists, the vertex belongs to its own neighbourhood.
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 (
Sedláček 1983). 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.
complete graphKn is locally Kn-1. The only graphs that are locally complete are disjoint unions of complete graphs.
Turán graphT(rs,r) is locally T((r-1)s,r-1). More generally any Turán graph is locally Turán.
chromatic graph is locally (k-1)-chromatic. Every locally k-chromatic graph has chromatic number (
If a graph family F is closed under the operation of taking induced subgraphs, then every graph in F is also locally F. For instance, every
chordal graph is locally chordal; every
perfect graph is locally perfect; every
comparability graph is locally comparable.
Claw-free graphs are the graphs that are locally co-
triangle-free; that is, for all vertices, the
complement graph of the neighbourhood of the vertex does not contain a triangle. A graph that is locally H is claw-free if and only if the
independence number of H is at most two; for instance, the graph of the regular icosahedron is claw-free because it is locally C5 and C5 has independence number two.
For a set A of vertices, the neighbourhood of A is the union of the neighbourhoods of the vertices, and so it is the set of all vertices adjacent to at least one member of A.
A set A of vertices in a graph is said to be a module if every vertex in A has the same set of neighbours outside of A. Any graph has a uniquely recursive decomposition into modules, its
modular decomposition, which can be constructed from the graph in
linear time; modular decomposition algorithms have applications in other graph algorithms including the recognition of