2017/04/05 by Gregory Gutin, Gutin, Gregory, Ruijuan Li +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Rings, Modules, and Algebras #Advanced Topology and Set Theory
paper · pdf · doi:10.48550/arxiv.1704.01389
Seymour's second neighbourhood conjecture asserts that every oriented graph has a vertex whose second out-neighbourhood is at least as large as its out-neighbourhood. In this paper, we prove that the conjecture holds for quasi-transitive oriented graphs, which is a superclass of tournaments and transitive acyclic digraphs. A digraph D is called quasi-transitive is for every pair xy,yz of arcs between distinct vertices x,y,z, xz or zx ("or" is inclusive here) is in D.