Please wait a minute...
高校应用数学学报
高校应用数学学报  2020, Vol. 35 Issue (2): 245-252    
    
准传递定向图上的Seymour点
李瑞娟, 史 杰, 张新鸿
1. 山西大学 数学科学学院, 山西太原 030006;
2. 太原科技大学 应用数学系, 山西太原 030024
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
 全文: PDF(324 KB)  
摘要： 有向图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二次邻域猜想;  扩张竞赛图    
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.
Key words: quasi-transitive oriented graphs    Seymour’s second neighbourhood conjecture    extended tournament
出版日期: 2020-07-07
CLC:  O157  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
李瑞娟
史 杰
张新鸿

引用本文:

李瑞娟, 史 杰, 张新鸿. 准传递定向图上的Seymour点[J]. 高校应用数学学报, 2020, 35(2): 245-252.

LI Rui-juan, SHI Jie, ZHANG Xin-hong. Seymour vertices in a quasi-transitive oriented graph. Applied Mathematics A Journal of Chinese Universities, 2020, 35(2): 245-252.

链接本文:

http://www.zjujournals.com/amjcua/CN/    或    http://www.zjujournals.com/amjcua/CN/Y2020/V35/I2/245

[1] 张雪飞, 郑素文, 夏静, 曹贻鹏, 许飞. 度条件下的二部图的定向图[J]. 高校应用数学学报, 2019, 34(2): 239-.
[2] 李瑞娟, 韩婷婷. 正圆有向图中的弧不相交的Hamilton路和圈[J]. 高校应用数学学报, 2017, 32(4): 487-492.
[3] 侯远, 陈育栎, 郑艺容. 欧拉图的hyper-Wiener指标[J]. 高校应用数学学报, 2016, 31(2): 248-252.
[4] 王展青, 王力工, 梅若星, 翟若男, 董占鹏. 两类双圈图的Laplacian谱确定问题[J]. 高校应用数学学报, 2016, 31(1): 73-82.
[5] 吴宝丰, 庞琳琳, 沈富强. 关于图的最小$Q$-特征值[J]. 高校应用数学学报, 2016, 31(1): 83-89.
[6] 刘晓蓉, 郭曙光, 张荣. 不含$P_t$的非二部连通图的最小$Q$-特征值[J]. 高校应用数学学报, 2015, 30(4): 462-468.
[7] 邵旭彦, 张勇, 王成敏. 一类强对称自正交对角数独的存在性[J]. 高校应用数学学报, 2015, 30(4): 469-475.
[8] 何常香, 刘世琼. 星匹配数与(无符号)拉普拉斯特征值[J]. 高校应用数学学报, 2015, 30(3): 333-339.
[9] 郭巧萍, 崔丽楠. 正则多部竞赛图中任意弧的所有长度的外路[J]. 高校应用数学学报, 2014, 29(3): 288-294.
[10] 何春阳, 郭曙光. 不含三圈的$k$圈图的拟拉普拉斯和拉普拉斯谱半径[J]. 高校应用数学学报, 2014, 29(3): 295-302.
[11] 李啸芳, 曹海涛. 六类Oberwolfach问题OP$(4^{a},s^b)$的解[J]. 高校应用数学学报, 2014, 29(3): 303-309.
[12] 苏振华, 黄元秋. 五阶图与路$P_{n}$的联图交叉数[J]. 高校应用数学学报, 2014, 29(2): 245-252.
[13] 林丽美, 周书明, 许力. 交错群图$AG_n$的$h$-外连通度[J]. 高校应用数学学报, 2013, 28(4): 379-390.