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） ...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-/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.展开更多
基金partially supported by NNSFC(Grant No.11401353)TYAL of Shanxi and NSF of Shanxi Province(Grant No.2016011005)partially supported by China Scholarship Council
文摘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-/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.
