|
|
|
| Seymour vertices in a quasi-transitive oriented graph |
| LI Rui-juan, SHI Jie, ZHANG Xin-hong |
1. School of Math. Sci., Shanxi Univ., Taiyuan 030006;
2. Dept. of Appl. Math., Taiyuan Univ. of Sci. and Technol., Taiyuan 030024
|
|
|
|
Abstract A digraph D is called quasi-transitive if, for every triple x, y, z of distinct vertices of
D such that xy and yz are arcs of D, there is at least one are between x and z. Seymour’s second
neighbourhood conjecture asserts that every oriented graph D has a vertex v such that d+D(x) 6 d++D (x),
where an oriented graph is a digraph with no cycle of length two. A vertex that satisfies Seymour’s
second neighbourhood conjecture is called a Seymour vertex. Fisher proved that Seymour’s second
neighbourhood conjecture restricted to tournaments is true, where any tournament contains at least
one Seymour vertex. Havet and Thomass′e proved that a tournament T with no vertex of out-degree
zero has at least two Seymour vertices. Observe that quasi-transitive oriented graphs is a superclass of
tournaments. In this paper, Seymour’s second neighbourhood conjecture on quasi-transitive oriented
graphs is the core problem. Notice the relationship between Seymour vertices of a quasi-transitive
oriented graph and an extended tournament. It is proved that the conjecture is true for quasi-transitive
oriented graphs. Furthermore, every quasi-transitive oriented graph has at least a Seymour vertex and
every quasi-transitive oriented graph with no vertex of out-degree zero has at least two Seymour vertices.
|
|
Published: 07 July 2020
|
|
|
准传递定向图上的Seymour点
有向图D是准传递的, 如果对D中任意三个不同的顶点x, y和z, 只要在D中存
在弧xy, yz, x和z之间就至少存在一条弧. Seymour二次邻域猜想为: 在任何一个定向
图D中都存在一个顶点x, 满足d+D(x) 6 d++D (x). 这里, 定向图是指没有2圈的有向图.
称满足Seymour二次邻域猜想的点为Seymour点. Fisher证明了Seymour二次邻域猜想
适用于竞赛图, 也就是每个竞赛图至少包含一个Seymour点. Havet和Thomass′e证明
了, 无出度为零的点的竞赛图至少包含两个Seymour点. 注意到, 竞赛图是准传递有向
图的子图类. 研究Seymour二次邻域猜想在准传递定向图上的正确性, 通过研究准传
递定向图与扩张竞赛图的Seymour点之间的关系, 证明了准传递定向图上Seymour二
次邻域猜想的正确性, 得到: 每个准传递定向图至少包含一个Seymour点; 无出度为零
的点的准传递定向图至少包含两个Seymour点.
关键词：
准传递定向图,
Seymour二次邻域猜想,
扩张竞赛图
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
