Neighbour of a set on a graph

graph theoryterminology

Given a (simple) graph, the neighbours of a vertex are the adjacent vertices. For a given set of vertices $S$, the set of neighbours of $S$ is the union of the neighbours of its vertices. But I find natural to consider (and in fact I need to use) also the "strict neighbourgs" (my notation) of $S$ as the intersection of neighbours of the vertices, with the usual convention that the intersection over the empty set is the total set. Does it have a name, or some reference?

In fact I need to consider this notion but for a simple bipartite graph, with the only diference with the general case that I will consider only subsets on one of the parts, and then the "strict neighbours" of the empty set as a subset of one part is the other part.

Best Answer

A reasonable term for the simple case, by analogy with other uses of the adjective, would be the common neighbours (or common neighbourhood if you want to talk about the set rather than its elements). A web search for graph common neighbours or graph common neighbourhood shows that the term has been coined independently by other people in the past.

Given the neighbourhood properties of bipartite graphs, I don't see any reason that the term wouldn't extend naturally to your proposed special case.

Related Question