准传递定向图上的Seymour点  

Seymour vertices in a quasi-transitive oriented graph

作　　者：李瑞娟[1] 史杰 张新鸿[2] LI Rui-juan;SHI Jie;ZHANG Xin-hong(School of Math.Sci.,Shanxi Univ.,Taiyuan 030006,China;Dept.of Appl.Math.,Taiyuan Univ.of Sci.and Technol.,Taiyuan 030024,China)

机构地区：[1]山西大学数学科学学院,山西太原030006 [2]太原科技大学应用数学系,山西太原030024

出　　处：《高校应用数学学报（A辑）》2020年第2期245-252,共8页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：山西省优秀青年基金(201901D211197);山西省自然科学基金(201801D121013)。

摘　　要：有向图D是准传递的,如果对D中任意三个不同的顶点x, y和z,只要在D中存在弧xy, yz, x和z之间就至少存在一条弧. Seymour二次邻域猜想为:在任何一个定向图D中都存在一个顶点x,满足d^+D(x)d^++D(x).这里,定向图是指没有2圈的有向图.称满足Seymour二次邻域猜想的点为Seymour点. Fisher证明了Seymour二次邻域猜想适用于竞赛图,也就是每个竞赛图至少包含一个Seymour点. Havet和Thomassé证明了,无出度为零的点的竞赛图至少包含两个Seymour点.注意到,竞赛图是准传递有向图的子图类.研究Seymour二次邻域猜想在准传递定向图上的正确性,通过研究准传递定向图与扩张竞赛图的Seymour点之间的关系,证明了准传递定向图上Seymour二次邻域猜想的正确性,得到:每个准传递定向图至少包含一个Seymour点;无出度为零的点的准传递定向图至少包含两个Seymour点.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)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é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.

关 键 词：准传递定向图 Seymour二次邻域猜想 扩张竞赛图 

分 类 号：O157[理学—数学]