多部竞赛图中包含在圈中的孤

摘要

多部竞赛图无疑是有向图中一类重要的图，并且它已经被广泛研究.竞赛图是顶点数为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时是正确的.

目录

摘要

主要符号表

第一章 绪论

1．1 有向图中的一些基本概念

1．2 问题的提出和内容的安排

第二章 多部竞赛图中的相关结果

2．1 竞赛图中的一些已知结果

2．2 强多部竞赛图中有向路和有向圈问题的研究现状

第三章 强多部竞赛图中包含在一些圈中的弧

3．1 预备知识

3．2 强多部竞赛图中包含在一些圈中的弧

第四章 强多部竞赛图中包含弧或路的圈

4．1 问题的提出和预备知识

4．2 预备知识

4．3 强多部竞赛图中包含一些弧的圈

4．4 强竞赛图中包含一条路的圈

第五章 多部竞赛图中的强子竞赛图

5．1 问题的提出和研究现状

5．2 预备知识

5．3 多部竞赛图中的强子竞赛图

总结

参考文献

攻读博士学位期间的主要研究成果

致谢

个人简况及联系方式

声明