论文部分内容阅读
多部竞赛图无疑是有向图中一类重要的图,并且它已经被广泛研究.竞赛图是顶点数为c的c-部竞赛图.关于竞赛图中有向路和有向圈问题的研究非常深入而且成果丰硕.将竞赛图的结果推广到多部竞赛图中是研究多部竞赛图的有效途径之一.一个向图D的Hamiltonian圈指的是一个包含D的所有顶点的圈.称有向图D是泛圈的,如果它包含从3到|V(D)|的每个长度的圈.称有向图D的一个顶点(一条弧)是泛圈的,如果它属于每个l-圈(3≤l≤|V(D)|).称有向图D是顶点泛圈(弧泛圈)的,如果它的每个顶点(弧)是泛圈的.目前,在竞赛图的泛圈性、顶点泛圈性及弧泛圈性方面已有了很多结果.有向图D的一条从顶点x出发的弧被称为是x的一条外弧.如果一个顶点的所有外弧在D中都是泛圈的,则称这个顶点是外弧泛圈顶点.2000年,Yao,Guo和Zhang首次对竞赛图中顶点的外弧泛圈性作了讨论,证明了强竞赛图中外弧泛圈顶点的存在性.而对于强多部竞赛图,连Hamiltonian圈的存在都不能保证.因此,退一步讲,在c-部竞赛图中,我们考虑属于l-圈(3≤l≤c)的顶点(弧),以及属于顶点恰巧来自l(3≤l≤c)个不同部集的圈的顶点(弧).1994年,Moon证明了强竞赛图至少存在三条泛弧.考虑到Moon的结果,Volkmann在2007年提出的一个猜想:每个强c(c≥3)-部竞赛图至少包含三条弧,其中每条弧属于一个m-圈Cm,对每个m∈{3,4,...,c}.本文主要研究强多部竞赛图中上述弧的存在性,证明了Volkmann的猜想,从而推广了上述Moon的结果.2008年,Volkmann和Winzen关于正则多部竞赛图提出猜想:正则的c(c≥5)-部竞赛图D的每一个顶点包含在包含一个阶为p的强子竞赛图,对每个p∈{3,4,...,c}.本文给出c-竞赛图存在一个阶为c的强子竞赛图的一个充分条件.作为定理的一个推论,我们证明了Volkmann和Winzen的上述猜想当c≥16时是正确的.