second neighborhood problem
Statement
Let be an oriented graph: a finite directed graph with no self-loops, no parallel edges, and no directed cycle of length two (equivalently, for all at most one of and lies in ). For a vertex let
be the first neighborhood of , i.e. the set of vertices at directed distance one from , and let
be the second neighborhood of , i.e. the set of vertices at directed distance exactly two from . The sets and are disjoint and neither contains .
Then every oriented graph has a vertex with
In particular, this holds when is a tournament, i.e. an orientation of a complete graph.
Record
- Added
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.