The Second Neighbourhood for Quasi-transitive Oriented Graphs |
| |
Authors: | Rui Juan Li Bin Sheng |
| |
Institution: | 1. School of Mathematical Sciences, Shanxi University, Taiyuan 030006, P. R. China;2. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, P. R. China;3. Department of Computer Science, Royal Holloway, University of London, TW20 0EX Egham, UK |
| |
Abstract: | 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 quasitransitive 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. |
| |
Keywords: | Second neighbourhood quasi-transitive digraphs extended tournaments |
本文献已被 CNKI SpringerLink 等数据库收录! |
| 点击此处可从《数学学报(英文版)》浏览原始摘要信息 |
| 点击此处可从《数学学报(英文版)》下载免费的PDF全文 |
|