准传递定向图上的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二次邻域猜想、扩张竞赛图

所属期刊栏目：35

分类号：O157(代数、数论、组合理论)

资助基金：山西省优秀青年基金;山西省自然科学基金

在线出版日期：2020-06-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：245-252