|
11.
准传递定向图上的Seymour点
李瑞娟, 史 杰, 张新鸿
高校应用数学学报
2020, 35 (2):
245-252.
有向图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点.
|
|