竞赛图是无向完全图的定向图。称有向图D中的弧uv是泛圈的,如果对每个3≤k≤|V (D)|,它都包含在一个长为k的圈中。弧uv的旁路是一条从u到v的有向路。称有向图D中的弧uv是反向泛圈的,如果对每个2≤k≤|V (D)|-1,它都有一条长为k的旁路。Moon证明了每个强连通的竞赛图存在至少三条泛圈弧。文章在此基础上进一步研究了竞赛图中的反向泛圈弧的存在性,证明了顶点数n≥6的竞赛图至少包含一条反向泛圈弧,并刻画出至少存在一条反向泛圈弧的竞赛图。
科研之友
微信
新浪微博
Facebook
分享链接
