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 vertices adjacent to v, i.e., the graph composed of the vertices adjacent to v and all edges connecting vertices adjacent to v. For example, in the image to the right, the neighbourhood of vertex 5 consists of vertices 1, 2 and 4 and the edge connecting vertices 1 and 2.

A graph consisting of 6 vertices and 7 edges
For other meanings of neighbourhoods in mathematics, see Neighbourhood (mathematics). For non-mathematical neighbourhoods, see Neighbourhood (disambiguation).

The neighbourhood is often denoted NG(v) or (when the graph is unambiguous) N(v). 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 NG[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 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.

Local properties in graphs

In the octahedron graph, the neighbourhood of any vertex is a 4-cycle.

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 (Hell 1978, 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.

For example:

Neighbourhood of a set

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 comparability graphs.

See also

References

  • Fronček, Dalibor (1989), "Locally linear graphs", Mathematica Slovaca, 39 (1): 3–6, hdl:10338.dmlcz/136481, MR 1016323
  • Hartsfeld, Nora; Ringel, Gerhard (1991), "Clean triangulations", Combinatorica, 11 (2): 145–155, doi:10.1007/BF01206358.
  • Hell, Pavol (1978), "Graphs with given neighborhoods I", Problèmes combinatoires et théorie des graphes, Colloques internationaux C.N.R.S., 260, pp. 219–223.
  • Larrión, F.; Neumann-Lara, V.; Pizaña, M. A. (2002), "Whitney triangulations, local girth and iterated clique graphs", Discrete Mathematics, 258 (1–3): 123–135, doi:10.1016/S0012-365X(02)00266-2.
  • Malnič, Aleksander; Mohar, Bojan (1992), "Generating locally cyclic triangulations of surfaces", Journal of Combinatorial Theory, Series B, 56 (2): 147–164, doi:10.1016/0095-8956(92)90015-P.
  • Sedláček, J. (1983), "On local properties of finite graphs", Graph Theory, Lagów, Lecture Notes in Mathematics, 1018, Springer-Verlag, pp. 242–247, doi:10.1007/BFb0071634, ISBN 978-3-540-12687-4.
  • Seress, Ákos; Szabó, Tibor (1995), "Dense graphs with cycle neighborhoods", Journal of Combinatorial Theory, Series B, 63 (2): 281–293, doi:10.1006/jctb.1995.1020, archived from the original on 2005-08-30.
  • Wigderson, Avi (1983), "Improving the performance guarantee for approximate graph coloring", Journal of the ACM, 30 (4): 729–735, doi:10.1145/2157.2158.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.