The neighbourhood of a vertex set consists of all vertices adjacent to at least one vertex of .
A neighbour of a vertex in a graph is a vertex joined to by an edge. These vertices form the graph neighbourhood .
The closed neighbourhood of a vertex set is .
The external vertex boundary of a vertex set is
For comparisons at fixed , minimizing is equivalent to minimizing .
A common neighbour of vertices and is adjacent to both of them.
The common neighbourhood of a vertex set in a simple graph is the intersection of the open graph neighbourhoods:
Its vertices are adjacent to every member of . This differs from the union-neighborhood convention , which asks for adjacency to at least one member. The notation must distinguish these two operations.
In the path , vertices one and three have common neighbourhood . In a triangle, the endpoints of an edge have the third vertex as their unique common neighbor. Neither endpoint belongs to the intersection, because a simple graph has no loops.
Common-neighbor counts detect triangles and other dense local patterns. In a bipartite graph with parts , the common neighbourhood of a subset of lies in and identifies vertices simultaneously connected to the entire chosen subset.

Ancestors (5)

  1. Graph theory
  2. Foundations of mathematics
  3. Area of mathematics
  4. Mathematics
  5. Home

Synonyms (1)

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.