The Second Neighbourhood for Quasi-transitive Oriented Graphs

In 2006, Sullivan stated the conjectures: (1) every oriented graph has a vertex x such that d++(x) . d.(x); (2) every oriented graph has a vertex x such that d++(x)+d+(x) . 2d. (x); (3) every oriented graph has a vertex x such that d++(x) + d+(x) . 2 · min{d+(x), d. (x)}. A vertex x in D satisfying Conjecture (i) is called a Sullivan-i vertex, i = 1, 2, 3. A digraph D is called quasi-transitive if for every pair xy, yz of arcs between distinct vertices x, y, z, xz or zx (.or. is inclusive here) is in D. In this paper, we prove that the conjectures hold for quasi-transitive oriented graphs, which is a superclass of tournaments and transitive acyclic digraphs. Furthermore, we show that a quasi-transitive oriented graph with no vertex of in-degree zero has at least three Sullivan-1 vertices and a quasi-transitive oriented graph has at least three Sullivan-3 vertices unless it belongs to an exceptional class of quasi-transitive oriented graphs. For Sullivan-2 vertices, we show that an extended tournament, a subclass of quasi-transitive oriented graphs and a superclass of tournaments, has at least two Sullivan-2 vertices unless it belongs to an exceptional class of extended tournaments.