Neighbourhood (graph theory)

Neighbourhood (graph theory)
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).

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 induced subgraph of G consisting of all vertices adjacent to v and all edges connecting two such vertices. For example, the image shows a graph of 6 vertices and 7 edges. Vertex 5 is adjacent to vertices 1, 2, and 4 but it is not adjacent to 3 and 6. The neighbourhood of vertex 5 is the graph with three vertices, 1, 2, and 4, and one edge connecting vertices 1 and 2.

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.

Contents

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, Sedlacek 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:

  • Any complete graph Kn is locally Kn-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 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 locally C4 graph, the icosahedron is the unique locally C5 graph, and the Paley graph of order 13 is locally C6. Locally cyclic graphs other than K4 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 1981; Larrión, Neumann-Lara & Pizaña 2002; Malnič & Mohar 1992). Locally cyclic graphs can have as many as n2 − 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 neighborhood 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.

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 neighbors 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


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Neighbourhood (mathematics) — For the concept in graph theory, see Neighbourhood (graph theory). A set V in the plane is a neighbourhood of a point p if a small disk around p is contained in V …   Wikipedia

  • Neighbourhood (disambiguation) — A neighbourhood (American spelling neighborhood) is a part of a city or town. Neighbourhood may also refer to: Mathematics Neighbourhood (mathematics), a concept in topology Neighbourhood (graph theory), a grouping in graph theory the Moore… …   Wikipedia

  • Covering graph — In the mathematical discipline of graph theory, a graph C is a covering graph of another graph G if there is a covering map from the vertex set of C to the vertex set of G. A covering map f is a surjection and a local isomorphism: the… …   Wikipedia

  • List of mathematics articles (N) — NOTOC N N body problem N category N category number N connected space N dimensional sequential move puzzles N dimensional space N huge cardinal N jet N Mahlo cardinal N monoid N player game N set N skeleton N sphere N! conjecture Nabla symbol… …   Wikipedia

  • Moore neighborhood — The Moore neighborhood comprises eight cells which surround center C. In cellular automata, the Moore neighborhood comprises the eight cells surrounding a central cell on a two dimensional square lattice. The neighborhood is named after Edward F …   Wikipedia

  • Clustering coefficient — In graph theory, a clustering coefficient is a measure of degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real world networks, and in particular social networks, nodes tend to create tightly knit groups… …   Wikipedia

  • combinatorics — /keuhm buy neuh tawr iks, tor , kom beuh /, n. (used with singular v.) See combinatorial analysis. * * * Branch of mathematics concerned with the selection, arrangement, and combination of objects chosen from a finite set. The number of possible… …   Universalium

  • Covering space — A covering map satisfies the local triviality condition. Intuitively, such maps locally project a stack of pancakes above an open region, U, onto U. In mathematics, more specifically algebraic topology, a covering map is a continuous surjective… …   Wikipedia

  • topology — topologic /top euh loj ik/, topological, adj. topologically, adv. topologist, n. /teuh pol euh jee/, n., pl. topologies for 3. Math. 1. the study of those properties of geometric forms that remain invariant under c …   Universalium

  • Connected space — For other uses, see Connection (disambiguation). Connected and disconnected subspaces of R² The green space A at top is simply connected whereas the blue space B below is not connected …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”