On the Second Neighborhood Conjecture

Rui Xu1
1Department of Mathematics University of West Georgia, Carrollton, GA 30118, USA

Abstract

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.