Second neighborhood problem

In mathematics, the second neighborhood problem is an unsolved problem about oriented graphs posed by Paul Seymour.

Intuitively, it suggests that in a social network described by such a graph, someone will have at least as many friends-of-friends as friends.

Equivalently, it is a directed graph that has no self-loops, no parallel edges, and no two-edge cycles.

(also called its open neighborhood) consists of all vertices at distance one from

In 1990, Paul Seymour conjectured that, in every oriented graph, there always exists at least one vertex

The problem was first published by Nathaniel Dean and Brenda J. Latka in 1995, in a paper that studied the problem on a restricted class of oriented graphs, the tournaments (orientations of complete graphs).

[5] In the second neighborhood conjecture, the condition that the graph have no two-edge cycles is necessary, for in graphs that have such cycles (for instance the complete oriented graph) all second neighborhoods may be empty or small.

Fisher (1996) proved Dean's conjecture, the special case of the second neighborhood problem for tournaments.

For instance, if a directed graph has a sink, a vertex of out-degree zero, then the sink is automatically a Seymour vertex, because its first and second neighborhoods both have size zero.

of minimum out-degree is again a Seymour vertex, because for any edge from

[7] For arbitrary graphs with higher vertex degrees, the vertices of minimum degree might not be Seymour vertices, but the existence of a low-degree vertex can still lead to the existence of a nearby Seymour vertex.

Using this sort of reasoning, the second neighborhood conjecture has been proven to be true for any oriented graph that contains at least one vertex of out-degree ≤ 6.

[8] Random tournaments and some random directed graphs graphs have many Seymour vertices with high probability.

times as big as the first neighborhood, where is the real root of the polynomial