多部竞赛图中分量共轭圈和共轭圈

《多部竞赛图中分量共轭圈和共轭圈》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东大学博士学位论文多部竞赛图中的分量共轭圈与共轭圈何志红(山东大学数学与系统科学学院，山东，济南250100)指导教师t李圉君教授中文摘要众所周知，竞赛图作为有向图的一部分，具有比较丰富的理论，如1966147]，综述文章1978148]和【491，1981[so]，1994151]，和1996152]等．在这种情况下我们对竞赛图的推广图产生了浓厚地兴趣，并对其进行了深入地研究．1990年。Bang-Jemen对竞赛图作了—个非常有意义的推广，得到局部半完全有向图(10callysemieompletedigraphs)．如果—个有向

2、图中任意两个不同的点之间至少存在一条弧，则这个有向图是半完全的．如果一个有向图中任何一点的出邻集和入邻集的导出子图均是半完全的，则此有向图为局部半完全有向图．不含长为2的圈的局部半完全有向图称为局部竞赛图．半完全多部有向图(semicompletemultipartitedigraphs)是竞赛图的另一类非常有趣的扩展图．—个完全伽部图的每一条边被一条弧或者一对有公共顶点的相反的弧所代替得到的有向图被称为半完全静部有向图或半完全多部有向图．一个不包含长为2的圈的半完全多部有向图被称为多部竞赛图．竞赛图是每个部集恰有一个点的多部竞赛图．显

3、然，根据定义局部半完全有向图和半完全多部有向图这两类图均比竞赛图这类图更广泛，并且均包含竞赛图这类图．如果有向图D中存在两个不相交的圈C和∥使得V(D)=v(c)uy(∥)，则D是圈共轭的(cyclecomplementary)且G和∥是D的—对共轭圈(complementarycycles)．多部竞赛图的共轭圈的存在性依赖于多部竞赛图和它的正则图之间的差距是多少．因此，我们引进被Yeo给出的整体非正则度ig(D)和局部非正则度it(D)这两个参数．一个有向图D的整体非正则度ia(D)定义为％(D)=脚刊嬲)(d+(霉)，d一(g))-

4、蚱m矿i(1D)l(矿(伽-(洲)．如果io(D)=0，则D是正则的(regular)，并且如果站(D)≤1，则D是几乎正则的(almostregular)．—个有向图的局部非正则度为矗(D)，定义为缸(D)一倒ma(x功fd+(z)一d一(。)I山东大学博士学位论文如果idD)≤1，则D是局部几乎正则的(10callyalmostregular)．竞赛图的共轭圈问题几乎已经被Reid在1985年和Song在1993年完全解决．他们证明了对于所有的t∈{3，4，⋯，Iy(D)f一3)，每一个至少有8个点的2-连通的竞赛图D都包含一对长分

5、别为t和ly(D)I—t的共轭圈．几年以后，Guo和Volkmann推广这个结果到局部半完全有向图中．另外，Z．Song，K．Zhang，Manoussalds和J．Wang分别给出二部竞赛图中存在共轭圈的一些结果．2004年，Volkmann证明了每一个正则多部竞赛图都是圈共轭的，除非它属于正则多部竞赛图中的—个有限类．但是，除了竞赛图，二都竞赛图、局部半完全有向图和正则多部竞赛图以外的多部竞赛图的共轭圈的存在性问题仍然是open问题，并且这个问题看起来是相当困难的．于是我们首次给出。分量共轭圈(componentwisecomple

6、mentarycycles)”的定义l定义令K，K，⋯，K是有向图D的部集．如果在D中存在两个不相交的圈e和∥使得Wn∥(c)uy(∥))≠0，对于所有的i=1，2，．．．，c，则称G和∥为D的一对分量共轭圈．如果有向图D中存在两个分量共轭圈，则称D是圈分量共轭的(cyclecomponen-twisecomplementary)．本文主要是证明多部竞赛图中的分量共轭圈和共轭圈的存在性，共为五章．文章的开始是引言．在第二章中，我们首次给出分量共轭圈这样一个定义．根据定义知共轭圈也是分量共轭圈，于是该定义具有重要的意义．同时首次研究几类多

7、部竞赛图的分量共轭圈的存在性，得到以下重要的成果．首先，我们尝试着证明2-强连通多部竞赛图的分量共轭圈的存在性．注意到每一个2-强连通的多部竞赛图都包含一个3-圈．令C是2_强连通多部竞赛图D的—个3-圈．如果D—v(v)是强连通的，则D—y(回包含—个最长圈∥使得c和∥是D的一对分量共轭圈．我们主要是证明当D—v(c)不是强连通时D是否包含—对分量共轭圈?结论1令D是一个2-强连通的m部m≥6)竞赛图但不是竞赛图，C是D的一个3-圈且D—v(c)不是强连通的．对于D—v(c)唯一的强连通分支无圈序D1，D2，⋯，D。(Ot22)，如果

8、强连通分支中仅有某一个B包含圈而其它的分支分别仅由—个点构成，其中1