准传递定向图上的Seymour点

发布时间：2022-12-09 04:46

　　有向图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点. 

【文章页数】：8 页


本文编号：3714853