Neighbourhood (graph theory)

From Wikipedia, the free encyclopedia

For other meanings of neighbourhoods in mathematics, see Neighbourhood (mathematics). For non-mathematical neighbourhoods, see Neighbourhood (disambiguation).

In the mathematical area of graph theory, the neighbourhood of a vertex v in a graph G is the induced subgraph of G consisting of all vertices adjacent to v and all edges connecting two such vertices.

The neighbourhood is often denoted N_G(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 N_G[v]. When stated without any qualification, a neighbourhood is assumed to be open.

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, Sedlacek 1983). For instance, in the octahedron graph shown in the figure, each vertex has a neighborhood isomorphic to a cycle of four vertices, so the octahedron is locally C₄.

Neighborhoods are also used in the clustering coefficient of a graph, which is a measure of the average density of its neighborhoods.

[edit] Examples

• 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 (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 locally C₄ graph, the icosahedron is the unique 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 and Ringel 1981; Larrión et al 2002; Malnič and Mohar 1992). Locally cyclic graphs can have as many as n^{2 − o(1)} edges (Seress and Szabó 1995).

[edit] References

• Hartsfeld, N.; Ringel, G. (1991). "Clean triangulations". Combinatorica 11: 145–155. 

• Hell, Pavol (1978). "Graphs with given neighborhoods I". Colloque internationaux C.N.R.S., No. 260, Problems Combinatories et theorie des graphes: 219–223. 

• Larrión, F.; Neumann-Lara, V.; Pizaña, M. A. (2002). "Whitney triangulations, local girth and iterated clique graphs". Discrete Mathematics 258: 123–135. 

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

• Sedlacek, J. (1983). "On local properties of finite graphs". Graph Theory, Lagów: 242–247, Lecture Notes in Mathematics, no. 1018, Springer-Verlag. 

• Seress, Ákos; Szabó, Tibor (1995). "Dense graphs with cycle neighborhoods". Journal of Combinatorial Theory, Series B 63: 281–293. 

• Wigderson, Avi (1983). "Improving the performance guarantee for approximate graph coloring". Journal of the ACM 30 (4): 729–735. DOI:10.1145/2157.2158.