论文部分内容阅读
一个竞赛图是任何两个顶点均相邻的定向图.称有向图D是泛圈的,如果它包含从3到|V(D)|的每个长度的圈.称有向图D的一条弧是k泛的,如果它属于每个l-圈(k≤l≤|V(D)|).当k=3时,也称该弧是泛圈的.称有向图D中的顶点u是外弧泛圈点,如果它的每条外弧是泛圈的.本文主要研究强连通竞赛图中的外弧4泛圈点问题.在2000年,Yao等人首先提出并证明了每一个强连通竞赛图存在一点u使得u的每条外弧都是泛圈的.在2005年,Yeo证明了每一个3-强连通竞赛图中存在两个不相同的顶点x,y使得x与y的所有外弧都是泛圈的.在2006年,李瑞娟等人又证明了每个k强连通竞赛图至少包含k+1个外弧4泛圈点.在2010年,郭巧萍等人证明了每个k强连通竞赛图至少包含k+2个外弧5泛圈点.文章在前人的基础上主要讨论了2-强连通竞赛图和k(k≥3)-强连通竞赛图中的外弧4泛圈点的问题. 本文主要分为四章.第一章是预备知识,我们介绍了一些本文中将要用到的图论方面的基本概念和记号. 第二章回顾了竞赛图中相关的一些结果. 第三章,我们研究了2-强连通竞赛图中的外弧4泛圈点问题,主要结果如下: 设T是一个δ+(T)≥3的2-强连通竞赛图,M是T中外度最小的点的集合.若|M|≠3且对任意v∈M有σ(T-v)=2,则T中至少有四个外弧4泛圈点. 第四章,我们研究了k(k≥3)-强连通竞赛图中的外弧4泛圈点问题,主要结果如下: 设T是一个k(k≥3)-强连通竞赛图.若δ+(T)≥k+1,则T中至少有k+2个外弧4泛圈点.