Nonneighbors

Nonneighbors is a term used in graph theory to describe the vertices that are not adjacent to a given vertex. Specifically, in a graph G = (V, E) and a vertex v ∈ V, a nonneighbor of v is a vertex u ≠ v such that the edge (v, u) is not in E. Equivalently, the nonneighbors of v are the vertices in V that lie outside the closed neighborhood of v, N[v] = {v} ∪ N(v). The set of nonneighbors is V \ N[v], and its size is |V| − |N[v]| = n − (deg(v) + 1), where deg(v) is the degree of v.

Examples help illustrate the concept. In a graph with vertices {a, b, c, d, e} and edges {a–b, a–c}, the nonneighbors of a are d and e. If a vertex has degree d(v) = 2 in a graph of five vertices, the number of nonneighbors is 5 − (2 + 1) = 2.

Relation to other concepts. In the complement graph Ḡ, where edges exist precisely between nonadjacent pairs of G, the nonneighbors of v in G correspond to the neighbors of v in Ḡ. In directed graphs, one distinguishes nonoutneighbors (not connected by an outgoing edge from v) and, similarly, non inneighbors, depending on the direction of edges.

Properties and notes. The concept is inherently relative to a chosen vertex and the underlying graph structure. Nonneighbors are often used in discussions of local neighborhoods, link prediction, or clustering analyses, where potential connections or independence among distant vertices are of interest. They should not be confused with nonadjacent vertices in a global sense, which refers to pairs of vertices that are not connected by an edge, a notion that may be considered without reference to a specific vertex.