论文部分内容阅读
竞赛图无疑是有向图中一类非常重要的图,并且它已经被广泛研究.关于竞赛图中有向路和有向圈问题的研究非常深入而且成果丰硕.称有向图D是泛圈的,如果它包含从3到|V(D)|的每个长度的圈.称有向图D的一个顶点(一条弧)是k泛的,如果它属于每个l-圈(k≤l≤|V(D)|).当k=3时,也称该顶点(弧)是泛圈的.称有向图D是顶点泛圈(弧泛圈)的,如果它的每个顶点(弧)是泛圈的.对某个k∈{3,4,…,|V(D)|},称有向图D是弧-k-圈的,如果D的每条弧都包含在一个长为k的圈中.显然,有向图D是弧泛圈的当且仅当对每个k=3,4,…,|V(D)|,它是弧-k-圈的.目前,在竞赛图的泛圈性、顶点泛圈性及弧泛圈性方面已有了很多结果.有向图D的一条从顶点x出发的弧被称为是x的一条外弧.如果一个顶点的所有外弧在D中都是k泛的,则称这个顶点是外弧k泛顶点.当k=3时,也称该顶点是外弧泛圈顶点.2000年,Yao,Guo和Zhang首次对竞赛图中顶点的外弧泛圈性作了讨论,证明了强竞赛图中外弧泛圈顶点的存在性.本文主要研究强竞赛图中顶点的外弧泛圈性问题. 本文共分五章.第一章介绍了有向图中的一些相关的基本概念以及论文内容的安排. 第二章回顾了竞赛图中的一些相关结果. 第三章研究了强竞赛图中外弧泛圈顶点的个数.在2000年,Yao,Guo和Zhang证明了每个强竞赛图T都包含一个外弧泛圈顶点.同时他们提出一个猜想:每个k-强竞赛图至少存在k个这样的顶点.现在已经证明了该猜想对k=1,2,3是对的.然而,由于Yeo给出的下面的例子,这个猜想对k≥4是不成立的.设T1,T2和T3都是阶至少为k的可迁竞赛图.T是在Ti之间添加弧得到的一个竞赛图,使得T1(→)T2(→)T3(→)T1.显然T是k-强的.由于Ti中的任何一条弧都不在T的一个3-圈中,所以仅有在每个Ti(i=1,2,3)中出度为零的顶点是T的外弧泛圈顶点.但是Yeo提出的下列猜想可能是正确的:每个2-强竞赛图至少包含3个外弧泛圈顶点.在3.2节,我们证明了Yeo的猜想是成立的.另外,对于最小出度为1的强竞赛图,Yao等人找到一个强竞赛图的无限类使得其中每个强竞赛图恰包含一个外弧泛圈顶点.那么我们自然要问:对于最小出度至少为2的强竞赛图包含几个外弧泛圈顶点呢?在3.3节,我们证明了连通度为1且最小出度至少是2的强竞赛图也至少包含3个外弧泛圈顶点,并举例说明了这个结果的最佳可能性.结合3.2和3.3节的这两个结论,我们得到具有最小出度至少是2的强竞赛图至少包含3个外弧泛圈顶点. 第四章研究了恰有3个外弧泛圈顶点的强竞赛图.Yeo在2005年给出一类例子说明对任意的正整数k,存在一类k-强竞赛图,使得其中每个竞赛图至多包含3个外弧泛圈顶点.那么除了这类例子以外,是否k-强竞赛图就包含k外弧泛圈顶点?本章中,我们给出了恰有3个外弧泛圈顶点的5-强竞赛图的一个必要条件,证明了恰有3个外弧泛圈顶点的5-强竞赛图是某一类图中的成员.设T1,T2和T3都是阶为k≥5的强竞赛图,满足u,v1和w1分别是T1,T2和T3中出度为零的顶点,且有(V(T1)-{u})→u,(V(T2)-{v1})→v1及(V(T3)-{w1})→w1.设T4是一个竞赛图.令T0是在Ti(i=1,2,3,4)之间添加弧得到的所有强竞赛图的集合,使得T1(→)T2(→)T3(→)T1且T4中的每个顶点都控制{u,v1,w1},其它的弧任意定向.设T是一个恰包含3个外弧泛圈顶点的5-强竞赛图,则T是T0中的一个成员.我们的结果表明,除T0以外,5-强竞赛图一定包含4个外弧泛圈顶点. 第五章讨论了k-强竞赛图中外弧5泛顶点的数目.Feng等人在2006年证明了k-强竞赛图(k≥3)至少包含k+1个外弧4泛顶点,我们证明了k-强竞赛图(k≥4)至少包含k+2个外弧5泛顶点.