多部竞赛图中的分量共轭圈与共轭圈

摘要

众所周知，竞赛图作为有向图的一部分，具有比较丰富的理论，如1966[47],综述文章1978[48]和[49]，1981[50]，1994[51]，和1996[52]等．在这种情况下我们对竞赛图的推广图产生了浓厚地兴趣，并对其进行了深入地研究。 1990年，Bang-Jensen对竞赛图作了一个非常有意义的推广，得到局部半完全有向图(locally semicomplete digraphs)．如果一个有向图中任意两个不同的点之间至少存在—条弧，则这个有向图是半完全的．如果一个有向图中任何一点的出邻集和入邻集的导出子图均是半完全的，则此有向图为局部半完全有向图．不含长为2的圈的局部半完全有向图称为局部竞赛图． 半完全多部有向图(semicomplete multipartite digraphs)是竞赛图的另一类非常有趣的扩展图．一个完全n-部图的每—条边被一条弧或者一对有公共顶点的相反的弧所代替得到的有向图被称为半完全n-部有向图或半完全多部有向图．—个不包含长为2的圈的半完全多部有向图被称为多部竞赛图．竞赛图是每个部集恰有一个点的多部竞赛图． 显然，根据定义局部半完全有向图和半完全多都有向图这两类图均比竞赛图这类图更广泛，并且均包含竞赛图这类图． 如果有向图D中存在两个不相交的圈G和C'使得V(D)=y(G)，UV(c')，则D是圈共轭的(cycle complementary)且C和C'是D的—对共轭圈(complementarycycles)． 多部竞赛图的共轭圈的存在性依赖于多部竞赛图和它的正则图之间的差距是多少．因此，我们引进被Yeo给出的整体非正则度i<,g>(D)和局部非正则度i<,t>(D)这两个参数．如果i<,g>(D)=0，则D是正则的(regular)，并且如果i<,g>(D)≤1，则D是几乎正则的(almost regular)．一个有向图的局部非正则度为i<,e>(D)，如果如i<,e>(D)≤1，则D是局部几乎正则的(locally almost regular)．竞赛图的共轭圈问题几乎已经被Reid在1985年和Song在1993年完全解决．他们证明了对于所有的t ∈{3，4，…，｜V(D)｜-3｝，每一个至少有8个点的2-连通的竞赛图D都包含一对长分别为t和｜y(D)｜-t的共轭圈．几年以后，Guo和Volkmann．推广这个结果到局部半完全有向图中．另外，Z．Song，K．Zhang，Manoussakis和J．Wang分别给出二部竞赛图中存在共轭圈的一些结果．2004年，Volkmann证明了每一个正则多部竞赛图都是圈共轭的，除非它属于正则多部竞赛图中的一个有限类．但是，除了竞赛图、二部竞赛图、局部半完全有向图和正则多部竞赛图以外的多部竞赛图的共轭圈的存在性问题仍然是open问题，并且这个问题看起来是相当困难的.于是我们首次给出“分量共轭圈(componentwise complementary cycles)”的定义: 定义令V<,1>,V<,2>…V<,C>是有向图D的部集．如果在D中存在两个不相交的圈C和C′使得V<,i>(V(C)u V(C′))≠φ，对于所有的i=1，2…，c，则称C和C′为D的一对分量共轭圈． 如果有向图D中存在两个分量共轭圈，则称D是圈分量共轭的(cycle componen-twise complementary)． 本文主要是证明多部竞赛图中的分量共轭圈和共轭圈的存在性，共为五章． 文章的开始是引言． 在第二章中，我们首次给出分量共轭圈这样一个定义．根据定义知共轭圈也是分量共轭圈，于是该定义具有重要的意义．同时首次研究几类多部竞赛图的分量共轭圈的存在性，得到以下重要的成果． 首先，我们尝试着证明2-强连通多部竞赛图的分量共轭圈的存在性．注意到每一个2-强连通的多部竞赛图都包含一个3-圈．令C是2-强连通多部竞赛图D的一个3-圈.如果D-V(C)是强连通的，则D-V(G)包含—个最长圈C′使得C和C′是D的一对分量共轭圈．我们主要是证明当D—V(D)不是强连通时D是否包含—对分量共轭圈? 结论1令D是一个2-强连通的n-部(n≥6)竞赛图但不是竞赛图，C是D的一个3-圈且D-V(C)不是强连通的．对于D-V(G)唯一的强连通分支无圈序D<,1>，D<,2>，…，D<,α>(α≥2)，如果强连通分支中仅有某一个D<,i>包含圈而其它的分支分别仅由一个点构成，其中1，D<,2>，…D<,α>(α≥2)，如果｜V(D<,α+1-i>)｜=1，D<,i>包含圈而其它的分支分别仅由一个点构成，其中i=1或者i=α，则D包含一对分量共轭圈。 结论3令D是一个2-强连通的n-部(n≥6)竞赛图但不是竞赛图，G是D的一个3-圈且D-V(C)不是强连通的．对于D-V(C)的唯一的强连通分支无圈序D<,1>,D<,2>，…，D<,α>(α≥2)，如果D<,1>和D<,α>分别包含圈而其它的分支分别仅由一个点构成，则D包含一对分量共轭圈．由结论1，结论2和结论3，我们得到下面的结论． 结论4令D是一个2-强连通的n-部竞赛图但不是竞赛图(n≥6)，C是D的一个3-圈且D-v(C)是非强连通的．对于D-v(C)的唯一的强连通分支无圈序D<,1>，D<,2>，…，D<,a>(a≥2)。令D<,c>={D<,i>|D<,i>包含圈，i=1，2，…，α}和D<,c>={D<,1>，D<,2>，…，D<,α>)\D<,c>．如果d<,c>≠φ且D<,c>中的每一个元素分别仅由一个点构成，则D包含一对分量共轭圈． 其次，我们对局部几乎正则多部竞赛图进行研究，发现当它的所有的部集均有相等的基数时存在一对分量共轭圈，除非它属于局部几乎正则多部竞赛图的一个有限类．于是得到下面的结论： 结论5令D是一个局部几乎正则c_部(c≥3)竞赛图且|v(D)+≥6．如果D的所有部集的基数均相等，则D包含一对分量共轭圈，除非它同构于T<'1><,7>或者．D<,3,2>(如图1．1，图1．3)． 最后，我们考虑了一类特殊图“几乎正则3-部竞赛图”，得到如下结论； 结论6如果D是一个几乎正则3-部竞赛图且|v(D)|≥6，则D包含一对分量共轭圈，除非D同构于D<,3,2>(如图1．3)． 下面是我们关于多部竞赛图中具有一定长度的共轭圈的一些结论． 第三章我们部分解决了Yeo在1999年提出的猜想，这对于完全解决Yeo猜想具有促进作用，结论如下： 结论7如果D是一个至少有8个点的c-部(c≥ 5)竞赛图，则D包含一对点不相交的长分别为5和|V(D)|-5的圈． 第四章我们首次将正则多部竞赛图的共轭圈问题推广到非正则多部竞赛图中考虑，得到一个重要结果，已有的许多重要的结果都可以由它推出． 结论8令D是一个至少有8个点的局部几乎正则的c-部(c≥3)竞赛图．如果它的部集具有相等的基数，则D包含一对点不相交的长分别为3和|v(D)|-3的圈． 由此结果很容易得到上面的结论5是成立的．由于每一个正则多部竞赛图都是一个部集具有相同基数的局部几乎正则的多部竞赛图，因此得到以下两个推论． 推论1(Volkmann[16])如果D是一个正则的3-部竞赛图且[v(D)]≥6，则D包含—对点不相交的长分别为3和[v(D)]-3的圈，除非D同构于．D3,2(如图1．3)． 推论2(Volkmann[15])令D是一个正则的c-部竞赛图且c≥4和[v(D)]≥6．则D包含两个长分别为3和[v(D)|-3的共轭圈,除非D同构于T<'1><,7>，D<,4,2>，或者D<'*><'4,2>(如图1．1，图1．4，图1．5)． 同时将Yeo的猜想推广到更一般的情况，得到下面的猜想: 猜想令D是一个至少有8个点的局部几乎正则的c-部(c≥3)竞赛图．如果它的部集具有相等的基数，则对于每一个t∈{3，4，…，｜V(D)｜-3}，D都包含一对点不相交的长分别为亡和｜V(D)｜-t的圈．猜想如果D是一个至少有6个点的几乎正则c-部(c≥3)竞赛图，则D包含一对共轭圈，除非D属于多部竞赛图的一个有限类． 在论文的最后我们给出一些进一步需要解决的问题．

目录

文摘

英文文摘

论文说明：NOTATION INDEX

原创性声明及关于学位论文使用授权的声明

第一章引言

§1.1研究背景

§1.2术语和概念

§1.3关于有向图的一些结果

§1.4本文的主要结果

§1.5本文的创新点

第二章多部竞赛图中的分量共轭圈

§2.1引言

§2.2预备知识

§2.3一类多部有向图是圈分量共轭的

§2.4局部几乎正则多部竞赛图是圈分量共轭的

§2.5几乎正则3-部竞赛图是圈分量共轭的

第三章当c≥5且t=5时Yeo猜想的证明

§3.1引言

§3.2预备知识

§3.3主要结果

§3.4未解决的问题

第四章局部几乎正则多部竞赛图中的共轭圈

§4.1引言

§4.2局部几乎正则多部竞赛图是圈共轭的

§4.3 Open问题

第五章进一步需要研究的问题

参考文献

CURRICULUM VITAE

致谢