The Setting
Take a vertex of a finite oriented graph. Some vertices are reached from by a single arc; others are reached by a directed path of two arcs and not by one. Seymour’s second-neighborhood conjecture asserts that every finite oriented graph has a vertex with at least as many vertices of the second kind as of the first.
The library defines the notions this conjecture is made of, for a digraph on a finite vertex set: an oriented graph, the first and second out-neighborhoods and of a vertex , a good vertex, and the second-neighborhood conjecture for a single digraph, the property that Seymour’s conjecture asserts of every finite oriented graph.
The Definition
Definition 1. Let be a digraph on a finite vertex set , with for an arc from to ; loops are allowed.
The digraph is oriented when it has no loop and no pair of opposite arcs: (1)✦
The first out-neighborhood of a vertex of is the set of the out-neighbors of : (2)✦
The second out-neighborhood of a vertex of is the set of the vertices at directed distance exactly two from : (3)✦
A vertex of is good when its second out-neighborhood is at least as large as its first: (4)✦
The digraph satisfies the second-neighborhood conjecture when it has a good vertex: (5)✦
What Is Checked
The five definitions are stated over a digraph on a finite vertex set with any set of arcs, loops included, and (2) to (4) over a vertex of as well; the neighborhoods and , good vertices and the second-neighborhood conjecture (5) are defined for every such digraph, oriented or not.