Neighbourhood (graph theory)

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 C₄.

For example:

• Any complete graph K_n is locally K_n-1. The only graphs that are locally complete are disjoint unions of complete graphs.
• A Turán graph T(rs,r) is locally T((r-1)s,r-1). More generally any Turán graph is locally Turán.
• Every planar graph is locally outerplanar. However, not every locally outerplanar graph is planar.
• A graph is triangle-free if and only if it is locally independent.
• Every k-chromatic graph is locally (k-1)-chromatic. Every locally k-chromatic graph has chromatic number ${\displaystyle O({\sqrt {kn}})}$ (Wigderson 1983).
• 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.
• A graph is locally cyclic if every neighbourhood is a cycle. For instance, the octahedron is the unique connected locally C₄ graph, the icosahedron is the unique connected locally C₅ graph, and the Paley graph of order 13 is locally C₆. Locally cyclic graphs other than K₄ are exactly the underlying graphs of Whitney triangulations, embeddings of graphs on surfaces in such a way that the faces of the embedding are the cliques of the graph (Hartsfeld & Ringel 1991; Larrión, Neumann-Lara & Pizaña 2002; Malnič & Mohar 1992). Locally cyclic graphs can have as many as ${\displaystyle n^{2-o(1)}}$ edges (Seress & Szabó 1995).
• 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 C₅ and C₅ has independence number two.
• The locally linear graphs are the graphs in which every neighbourhood is an induced matching (Fronček 1989).

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.

• Markov blanket
• Moore neighbourhood
• Von Neumann neighbourhood
• Second neighborhood problem
• Vertex figure, a related concept in polyhedral geometry

• 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.