Seymour's Second Neighborhood Conjecture


Home
Notations & definitions
The open problem
Incorrect proofs
Special cases
Correct(?) proofs
Related problems
Other results
About this website

The open problem

A problem in graph theory that has still remained unsolved is Seymour's Second Neighborhood Conjecture (SSNC). Sometimes, this open problem is referred to simply as Seymour's Conjecture, but since there is another surmise which is also called Seymour's Conjecture, the ambiguous designation will be avoided on this website.

SSNC states the following:

For every oriented graph there exists a vertex whose out-degree at least doubles when the oriented graph is squared.


SSNC can also be formulated as a conjecture which states that for every oriented digraph there exists at least one vertex u such that u has at least as many neighbours at distance 2 as it has at distance 1.

Example

The two graphs displayed here are an example of the abovementioned conjecture. The oriented graph on the right is the square of the oriented graph on the left. As can be seen, the vertices A, B, C, E and G satisfy the property that the out-degree of these vertices has at least been doubled. Hence, the graph on the left satisfies SSNC.

It follows from this example that if an oriented graph contains a vertex with 0 out-going edges, i.e. a vertex whose out-degree is 0, the graph automatically satisfies SSNC. For if there are no out-going edges in the vertex, there cannot be out-going edges in the square of the graph either.


Back to top