论文部分内容阅读
有向图是图论的一个重要分支,其理论成果在诸多领域有着广泛的应用.竞赛图是有向图中结构最好的一类图,已经得到广泛研究且成果丰硕.1968年,Moon首次引进竞赛图的一类推广图一多部竞赛图.从此多部竞赛图被受到广泛关注.图中圈的数目和长度是刻画图结构的重要指标,很多学者多年来一直致力于多部竞赛图中圈的研究.然而,由于多部竞赛图结构的复杂,使得竞赛图中的很多圈方面的结果没有被推广到多部竞赛图中.1999年,郭余宝教授提出外路的概念,以自然的方式推广了有向图中的圈.有向图中一个顶点x(或弧xy)的一条外路是指起始于x(或xy)的一条路使得x控制这条路的终点仅当终点也控制x.一条长为k的外路称为k-外路.目前,关于外路的研究结果还非常之少. Volkmann(Discrete Math.307(2007)3097-3129)总结了几十年来多部竞赛图圈和外路方面的几乎所有的结果,同时也提出很多未解决的猜想和问题.针对这些猜想和问题,本文分四章来进一步研究多部竞赛图. 第一章是绪论.主要介绍了有向图的一些基本概念及该论文的内容安排. 第二章主要研究正则3-部竞赛图中的圈.对于c-部竞赛图的圈的研究大多都是对c≥4来讨论的.对于3-部竞赛图的结论还非常少.这一章,我们证明了:如果D是一个r-正则3-部竞赛图(r≥3),则D>中每条弧都被包含在一个6-或7-圈中,该结果推广了Volkmann在2006年得到的结果. 第三章主要研究正则多部竞赛图中的圈和外路.我们研究了正则c-部(c≥8)竞赛图中每条弧的外路,推广了郭余宝教授在1999年得到的结果.我们也给出了每条弧都包含在Hamilton圈的一类正则多部竞赛图. 第四章主要研究几乎正则多部竞赛图中的圈和外路.我们证明了:如果D是几乎正则c-部(c≥8)竞赛图,每个部集至少包含两个点.则对每个k∈{3,4,...,|V(D)|-1},D中每条弧存在一(k-1)-或k-外路.进一步,当D是一个几乎正则c-部(c≥>8)竞赛图,且每个部集包含相同数目的顶点时,对每个k∈{3,4,...,|V(D)|-1},D中每条弧包含在一个k-或(k+1)-圈中.