TOPICS
Search

Graph Neighborhood


The graph neighborhood of a graph vertex v is terminology whose convention must be specified. The open graph neighborhood N(v) consists of the vertices adjacent to v, excluding v itself. The closed neighborhood N[v]=N(v) union {v} also includes v. Some sources use "graph neighborhood" specifically for N[v], while others use "neighborhood" for N(v).

More generally, the ith neighborhood of v is the set of all vertices at graph distance i from v.

The subgraph induced by the neighborhood of a graph from vertex v is called the neighborhood graph.

The term "graph neighbors" generally means vertices adjacent to v excluding v itself (Brouwer et al. 1989).

For a simple graph G on n vertices with average vertex degree cn, where 0<=c<1, and any integer 2<=k<=n, there are k distinct vertices u_1, ..., u_k whose open neighborhoods satisfy

 | union _(i=1)^kN(u_i)|>=nmin{1-(1-c)^k,sqrt(c)}.

This bound is asymptotically sharp for fixed k and c in (0,1). The two terms arise from random graphs G(n,c) and from a complete graph on about sqrt(c)n vertices together with isolated vertices, respectively (Pach 2026).


See also

Closed Neighborhood, Dominating Set, Graph Distance Graph, Irredundant Set, Local Graph, Neighborhood, Neighborhood Graph, Open Graph Neighborhood

Explore with Wolfram|Alpha

References

Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.Pach, J. "What Fraction of the Vertex Set of a Graph Can Be Covered by k Neighborhoods?" Elec. J. Combin. 33, P4.42, 2026. https://doi.org/10.37236/15672.

Referenced on Wolfram|Alpha

Graph Neighborhood

Cite this as:

Weisstein, Eric W. "Graph Neighborhood." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphNeighborhood.html

Subject classifications