nonoutneighbors

In graph theory, for a directed graph G = (V, E), the out-neighborhood N^+(v) of a vertex v ∈ V is the set of vertices w for which there is a directed edge from v to w, i.e., N^+(v) = { w ∈ V | (v, w) ∈ E }. The nonoutneighbors of v are the vertices not connected by an outgoing edge from v, i.e., the complement of the out-neighborhood: nonoutneighbors(v) = V \ N^+(v).

The precise form of nonoutneighbors depends on conventions about self-loops. If loops are allowed and (v, v) ∈ E, then v may be included in N^+(v); consequently, it may or may not be included in nonoutneighbors(v). A common convention is to exclude the vertex itself, defining nonoutneighbors(v) = { w ∈ V \ {v} | (v, w) ∉ E }. Under this convention, nonoutneighbors are exactly the vertices other than v that are not reachable from v in one step.

Example: In a directed graph with vertices {a, b, c, d} and edges a → b, a → c, b → d, the out-neighborhood of a is N^+(a) = {b, c}. The nonoutneighbors of a (excluding a itself) would be {d}, since a has no edge to d and there is no edge from a to itself unless specified.

Relation to other concepts: nonoutneighbors form the complement of the out-neighborhood within the vertex set V. They relate to the ith row of the adjacency matrix A of G by indicating the positions w where A[v, w] = 0. This concept is useful in analyses of one-step reachability, in degree-based measures, and in algorithms that consider non-adjacent vertices.

See also: out-neighborhood, in-neighborhood, adjacency matrix, reachability.