TOPICS
Search

Seymour's Second Neighborhood Conjecture


Seymour's second neighborhood conjecture asserts that every nonempty finite simple directed graph with no pair of opposite edges has a graph vertex v satisfying

 |N_1^+(v)|<=|N_2^+(v)|,

where N_1^+(v) consists of the out-neighbors of v and N_2^+(v) consists of the vertices at directed distance exactly two from v. The latter excludes v and all members of N_1^+(v).

The distinct Seymour conjecture concerns powers of Hamiltonian cycles in undirected graphs.


See also

Graph Neighborhood, Oriented Graph, Seymour Conjecture

Explore with Wolfram|Alpha

References

Fidler, D. and Yuster, R. "Remarks on the Second Neighborhood Problem." J. Graph Th. 55, 208-220, 2007. https://doi.org/10.1002/jgt.20229.

Cite this as:

Weisstein, Eric W. "Seymour's Second Neighborhood Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SeymoursSecondNeighborhoodConjecture.html

Subject classifications