Seymour’s Second Neighborhood Conjecture claims that every simple digraph has a vertex whose first neighborhood is at most as large as its second neighborhood. We confirm this conjecture for neighbor-connection free simple digraphs and distance-two simple digraphs. As a consequence, the conjecture is true for triangle-free digraphs and \(4\)-cycle free digraphs.
Keywords: first neighborhood; second neighborhood; triangle free digraph.
Citation
Rui Xu. On the Second Neighborhood Conjecture[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 088. 143-146. .