Seymour's 2nd Neighborhood Conjecture

Originator(s): P. Seymour (Princeton Univ.)

Definitions: In a digraph G, let N+(v) denote the successors of a vertex v, and let N++(v) denote the successors of vertices in N+(v) that are not in N+(v).

Conjecture: If G is a simple digraph with no cycle of length at most 2, then G has a vertex v such that |N++(v)| >= |N+(v)|.

Comments/Partial results: The special case when G is a tournament was conjectured by Dean and proved by Fisher [F]. Fisher's proof uses Farkas' Lemma and averaging arguments. A combinatorial proof appears in [HT] using median orders, where a median order of a tournament T is a transitive tournament on V(T) having the most edges in common with T. This proof obtains not one but two of the desired vertices.

Kaneko and Locke [KL] proved this conjecture for digraphs having a vertex with outdegree at most 6. Godbole, Cohn, and Wright [GCW] have proved that the conjecture holds for almost all digraphs.

Chen, Shen, and Yuster [CSY] proved that for every digraph, there is a vertex v such that |N++(v)| >= r|N+(v)|, where r is the solution of 2x3+x2=1 (about .657). They find such a vertex that is a vertex of minimum degree or is a successor of a vertex of minimum degree. They state a further improvement to .678.

Seymour's conjecture implies a special case of the Caccetta-Häggkvist Conjecture.

[CS] Chen, G.; Shen, J.; Yuster, R. Second neighborhood via first neighborhood in digraphs, Annals of Combinatorics, 7 (2003), 15--20.
[F] Fisher, David C. Squaring a tournament: a proof of Dean's conjecture. J. Graph Theory 23 (1996), no. 1, 43--48.
[GCW] Godbole, A; Cohn, Z; Wright, E. Probabilistic Versions of Seymour's Distance Two Conjecture, to appear.
[HT] Havet, F.; Thomassé, S. Median orders of tournaments: a tool for the second neighborhood problem and Sumner's conjecture. J. Graph Theory 35 (2000), no. 4, 244--256.
[KL] Kaneko, Yoshihiro; Locke, Stephen C. The minimum degree approach for Paul Seymour's distance 2 conjecture. Proceedings of the Thirty-second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001). Congr. Numer. 148 (2001), 201--206.

Back to Index Page Link to Glossary