（运筹学与控制论专业论文）多部竞赛图中的分量共轭圈与共轭圈.pdf

山东大学博士学位论文 多部竞赛图中的分量共轭圈与共轭圈 何志红 ( 山东大学数学与系统科学学院，山东，济南2 5 0 1 0 0 ) 指导教师t 李圉君教授 中文摘要 众所周知，竞赛图作为有向图的一部分，具有比较丰富的理论，如1 9 6 6 1 4 7 ，综述 文章1 9 7 8 1 4 8 和【4 9 1 ，1 9 8 1 s o ，1 9 9 4 1 5 1 ，和1 9 9 6 1 5 2 等在这种情况下我们对竞赛图 的推广图产生了浓厚地兴趣，并对其进行了深入地研究 1 9 9 0 年。b a n g - j e m e n 对竞赛图作了个非常有意义的推广，得到局部半完全有 向图( 1 0 c a l l ys e m i e o m p l e t ed i g r a p h s ) 如果个有向图中任意两个不同的点之间至少 存在一条弧，则这个有向图是半完全的如果一个有向图中任何一点的出邻集和入邻 集的导出子图均是半完全的，则此有向图为局部半完全有向图不含长为2 的圈的局 部半完全有向图称为局部竞赛图 半完全多部有向图( s e m i c o m p l e t em u l t i p a r t i t ed i g r a p h s ) 是竞赛图的另一类非常 有趣的扩展图个完全伽部图的每一条边被一条弧或者一对有公共顶点的相反的弧 所代替得到的有向图被称为半完全静部有向图或半完全多部有向图一个不包含长为 2 的圈的半完全多部有向图被称为多部竞赛图竞赛图是每个部集恰有一个点的多部 竞赛图 显然，根据定义局部半完全有向图和半完全多部有向图这两类图均比竞赛图这类 图更广泛，并且均包含竞赛图这类图 如果有向图d 中存在两个不相交的圈c 和使得v ( d ) = v ( c ) u y ( ) ，则 d 是圈共轭的( c y c l ec o m p l e m e n t a r y ) 且g 和是d 的对共轭圈( c o m p l e m e n t a r y c y c l e s ) 多部竞赛图的共轭圈的存在性依赖于多部竞赛图和它的正则图之间的差距是多少 因此，我们引进被y e o 给出的整体非正则度i g ( d ) 和局部非正则度i t ( d ) 这两个参数 一个有向图d 的整体非正则度i a ( d ) 定义为 ( d ) = 脚刊嬲) ( d + ( 霉) ，d 一( g ) ) - 蚱m 矿i ( 1 d ) l ( 矿( 伽- ( 洲) 如果i o ( d ) = 0 ，则d 是正则的( r e g u l a r ) ，并且如果站( d ) 1 ，则d 是几乎正则的 ( a l m o s tr e g u l a r ) 个有向图的局部非正则度为矗( d ) ，定义为 缸( d ) 一倒m a ( x 功f d + ( z ) 一d 一( 。) i 山东大学博士学位论文 如果i d d ) 1 ，则d 是局部几乎正则的( 1 0 c a l l ya l m o s tr e g u l a r ) 竞赛图的共轭圈问题几乎已经被r e i d 在1 9 8 5 年和s o n g 在1 9 9 3 年完全解决他 们证明了对于所有的t 3 ，4 ，i y ( d ) f 一3 ) ，每一个至少有8 个点的2 - 连通的竞 赛图d 都包含一对长分别为t 和l y ( d ) i t 的共轭圈几年以后，g u o 和v o l k m a n n 推广这个结果到局部半完全有向图中另外，z s o n g ，k z h a n g ，m a n o u s s a l d s 和j w a n g 分别给出二部竞赛图中存在共轭圈的一些结果2 0 0 4 年，v o l k m a n n 证明了每一 个正则多部竞赛图都是圈共轭的，除非它属于正则多部竞赛图中的个有限类但是， 除了竞赛图，二都竞赛图、局部半完全有向图和正则多部竞赛图以外的多部竞赛图的 共轭圈的存在性问题仍然是o p e n 问题，并且这个问题看起来是相当困难的于是我们 首次给出。分量共轭圈( c o m p o n e n t w i s ec o m p l e m e n t a r yc y c l e s ) ”的定义l 定义令k ，k ，k 是有向图d 的部集如果在d 中存在两个不相交的圈e 和 使得w n ( c ) u y ( ) ) 0 ，对于所有的i = 1 ，2 ，c ，则称g 和为d 的一 对分量共轭圈 如果有向图d 中存在两个分量共轭圈，则称d 是圈分量共轭的( c y c l ec o m p o n e n - t w i s ec o m p l e m e n t a r y ) 本文主要是证明多部竞赛图中的分量共轭圈和共轭圈的存在性，共为五章 文章的开始是引言 在第二章中，我们首次给出分量共轭圈这样一个定义根据定义知共轭圈也是分 量共轭圈，于是该定义具有重要的意义同时首次研究几类多部竞赛图的分量共轭圈 的存在性，得到以下重要的成果 首先，我们尝试着证明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 ) 唯一的强连通分支无圈序 d 1 ，d 2 ，d 。( o t22 ) ，如果强连通分支中仅有某一个b 包含圈而其它的分支分别 仅由个点构成，其中1 i o t ，则d 包含一对分量共轭圈 结论2 令d 是个2 - 强连通的伽部( n 6 ) 竞赛图但不是竞赛图，g 是d 的 一个3 - 圈且d v ( c ) 不是强连通的对于d v ( c ) 的唯一的强连通分支无圈序 d l ，d 2 ，上) a ( a 之2 ) ，如果i y ( d 时l 一 ) i = 1 ，d i 包含圈而其它的分支分别仅由一 个点构成，其中i = 1 或者t = n ，则d 包含一对分量共轭圈 结论3 令d 是个2 _ 强连通的伽部( n 6 ) 竞赛图但不是竞赛图，g 是d 的 一个3 圈且d v ( c ) 不是强连通的对于d v ( c ) 的唯一的强连通分支无圈序 i i 山东大学博士学位论文 d l ，d 2 ，d 。( 口22 ) ，如果d l 和 口分别包含圈而其它的分支分别仅由一个点构 成，则d 包含一对分量共轭圈 由结论1 ，结论2 和结论3 ，我们得到下面的结论 结论4 令d 是一个2 - 强连通的伽部竞赛图但不是竞赛图( 札6 ) ，g 是d 的一个3 - 圈且d v ( c ) 是非强连通的对于d v ( c ) 的唯一的强连通分支无 圈序d 1 ，d 2 ，见( o t 2 ) ，令d c = d l 皿包含圈，i = 1 ，2 ，a 和皿= d l ，d 2 ，上k ) d c 如果) c 毋且三b 中的每一个元素分别仅由一个点构成，则 d 包含一对分量共轭圈， 。 其次，我们对局部几乎正则多部竞赛图进行研究，发现当它的所有的部集均有相 等的基数时存在一对分量共轭圈，除非它属于局部几乎正则多部竞赛图的个有限类 于是得到下面的结论。 结论5 令d 是一个局部几乎正则c 部( c 3 ) 竞赛图且l 矿( d ) i 6 如果d 的 所有部集的基数均相等，则d 包含一对分量共轭圈，除非它同构于碍或者岛，2 ( 如 图1 1 ，图1 3 ) 最后，我们考虑了一类特殊图。几乎正则3 - 部竞赛图”，得到如下结论t 结论6 如果d 是个几乎正则3 - 部竞赛图且l y ( d ) i 6 ，则d 包含一对分萤共 轭圈，除非d 同构于d 3 2 ( 如图1 3 ) ， 下面是我们关于多部竞赛图中具有一定长度的共轭圈的一些结论 第三章我们部分解决了y e o 在1 9 9 9 年提出的猜想。这对于完全解决y e o 猜想具 有促进作用，结论如下。 结论7 如果d 是个至少有8 个点的c 部( c25 ) 竞赛图，则d 包含一对点不 相交的长分别为5 和i y ( d ) i 一5 的圈 第四章我们首次将正则多部竞赛图的共轭圈阿题推广到非正则多部竞赛图中考虑， 得到个重要结果，已有的许多重要的结果都可以由它推出 结论8 令d 是个至少有8 个点的局部几乎正则的c _ 部( c 3 ) 竞赛图如果 它的部集具有相等的基数，则d 包含一对点不相交的长分别为3 和i y ( d ) l 一3 的圈 由此结果很容易得到上面的结论5 是成立的由于每一个正则多都竞赛图都是一 个部集具有相同基数的局部几乎正则的多部竞赛图，因此得到以下两个推论 推论1 ( v o l k m m m 【1 6 】) 如果d 是一个正则的3 - 部竞赛图且j y ( d ) l 6 ，则d 包含一对点不相交的长分别为3 和i y ( d ) 一3 的圈，除非d 同构于d 3 ，2 ( 如图1 3 ) 推论2 ( v o l k m a n n 【1 5 】) 令d 是一个正则的c _ 部竞赛图且c 4 和i y p ) f 6 则d 包含两个长分别为3 和l y ( d ) l 一3 的共轭圈，除非d 同构于碍，上) 4 0 ，或者 蛾2 ( 如图1 1 ，图1 4 ，图1 5 ) 同时将y e o 的猜想推广到更一般的情况，得到下面的猜想； 猜想令d 是一个至少有8 个点的局部几乎正则的c - 部( c 3 ) 竞赛图如果它 i i i 山东大学博士学位论文 的部集具有相等的基数，则对于每一个t 3 ，4 ，i y ( d ) i _ 3 ) ，d 都包含一对点不 相交的长分别为t 和i y ( d ) j t 的圈 猜想如果d 是个至少有6 个点的几乎正则c 部( c 23 ) 竞赛图，则d 包含一 对共轭圈，除非d 属于多部竞赛图的一个有限类 在论文的最后我们给出一些进一步需要解决的问题 关键词；多部竞赛图；共轭圈；分量共轭圈；正则的；局部几乎正则的 i v 山东大学博士学位论文 c o m p o n e n t w i s ec o m p l e m e n t a r yc y c l e sa n d c o m p l e m e n t a r yc y c l e si nm u l t i p a r t i t e 。i b u r n a m e n t s h ez h i - h o n g ( s c h o o lo fm a t h & s y s s d ，s h a n d o n gu n i v ，j i n a u2 5 0 1 0 0 ，p r c h i n a ) a d v i s o r , p r o f l ig u o - j u n a b s t r a c t a si ti sw e l lk n o w n ，t h ec l a s so ft o u r n a m e n t sh a sav e r yr i c ht h e o r ya n di ti st h e m o s tw e l l - s t u d i e dc l a 鹪o fd i g r a p h s ( 8 【4 7 】1 9 6 6a n dt h es u r v e ya r t i c l e s 4 8 1 ， 4 9 11 9 7 8 ， 1 5 0 1 9 8 1 ， 5 1 】1 9 9 4 ，a n d 5 2 】1 9 9 6e t c ) s o ，t h es t u d yo fi t sg e n e r a l i z a t i o n sh a sa l s o r e c e i v e dm u c hi n t e r e s tr e c e n t l y ( 蛾e g v o l k n m n nf 1 5 1a n d 【1 6 】) i n1 9 9 0b a n g - j e n s e ni n t r o d u c e dav e r yi n t e r e s t i n gg e n e r a l i z a t i o no ft o u r n a m e n t s t h ec l a s so f o c 柏l ys e m i c o m p e t ed i g r a p h s ad i g r a p hi ss e m i c o m p l e t ei ff o ra n yt w o d i s t i n c tv e r t i c e s ，t h e r ei sa t e a s to n ea r cb e i ；w e e nt h e m ad i g r a p hi sl o c a l l y , i n i c o m - p l e t 旭i ff o re v e r yv e r t e xz t h es e to fi n - n e i g h b o u r s 蠲w e l la st h es e to fo u t - n e i g h b o u r so f zi n d u c es e m i e o m p l e t ed i g r a p h s al o c a lt o u r n a m e n ti sa l o c a l l ys e m i c o m p l e t ed i g r a p h w i t h o u tad i r e c t e dc y c l eo fl e n g t h2 a n o t h e ri n t e r e s t i n gg e n e r a l i z a t i o no ft o u r n a m e n t si st h ec l a s so fs o - c a l l e ds e m i c o m - p l e t em u l t i p a r t i t ed i g r 印h 8 ad i g r a p ho b t a i n e db yr e p l a c i n ge a c he d g eo fac o m p l e t e n - p a r t i t eg r a p hw i t ha na r co rap a i ro fm u t u a l l yo p p o s i t ea r c s 硒t ht h e8 a i n ee n dv e t - r i c e si sc a l l e das e m i c o m p l e t en - p a r t i t 七d i g r a p ho ras e m i c o m p e t em u l t i p a r t i t ed i g r a p h am u l t i p a r t i t et o u r n a m e n ti sas e m i c o m p e t em u l t i p a r t i t ed i g r a p hw i t h o u tac y c l eo f l e n g t ht w o i ti sc l e a rt h a tat o u r n a m e n ti sam u l t i p a r t i t et o u r n a m e n t e a c ho fw h o s e p a r t i t es e tc o n t a i n se x a c t l yo n e v e r t e x 。 i ti so b v i o u st h a tt w oc l a s s e so fl o c a l l ys e m i e o m p l e t ed i g r a p h sa n ds e m i c o m p l e t e m u l t i p a r t i t ed i g r a p h sa r eb i g g e rt h a nt h a to ft o u r n a m e n t s 一ad i g r a p hdi sc y c l ec o m p l e m e n t a r yi ft h e r ee x i s tt w ov e r t e x - d i s j o i n tc y c l e sca n d s u c ht h a tv ( d ) = y ( u y ( ) t h e r e i n t o ，ca n d a r es a i dt ob e8p a i ro f c o m p l e m e n t a r yc y c l e so fd n es t a t e m e n to nt h ee x i s t e n c eo fc o m p l e m e n t a r yc y c l e sd e p e n d so nh o wm u c h am u l t i p a r t i t et o u r n a m e n td i f f e r sf r o mb e i n gr e g u l a r h e n c e ，w eu s et w op a r a m e t e r s i n t r o d u c e db yy e o h ed e f i n e st h el o c a li r r e g u l a r i t y 蠲 v 山东大学博士学位论文 a n dt h eg l o b a li r r e g u l a r i t y 矗( d ) - 剁m a ( x d ) i d + ( z ) 一d 一( z ) 站( d ) = m a x j 。m 。a x d ) ( d + ( z ) , d - 0 ) ) 一蚱m 矿i ( n d ) ( d + ( 暑，) , d - 白) ) i ) i ti sc l e a rt h a tq ( d ) i g ( d ) i fi u ( d ) = 0 ，t h e ndi sr e g u l a r ，a n di fi s ( d ) 1 ，t h e ndi sc a l l e da l m o s tr e g u l a r i fi t ( d ) 墨1 ，t h e ndi sc a l l e dl o c a l l ya l m o s tr e g u l a r j 。 t h ep r o b l e mo f c o m p l e m e n t a r yc y c l e si nt o u r n a m e n t sw a sa l m o s tc o m p l e t e l ys o l v e d b yr e i di n1 9 8 5a n db ys o n gi n1 9 9 3 t h e s ea u t h o r sp r o v e dt h a te v e r y2 - c o n n e c t e d t o u r n a m e n tdo na tl e a s t8v e r t i c e sh a sc o m p l e m e n t a r yc y c l e so f l e n g t hta n di y ( d ) i _ t f o ra l lt 3 ，4 ，l y ( d ) i 一3 s o m ey e a r sl a t e r ，g u oa n dv o l k m a n ne x t e n d e d t h i sr e s u l tt ol o c a l l ys e m i c o m p l e t ed i g r a p h s i na d d i t i o n ，t h e r ea r es o m er e s u l t so n c o m p l e m e n t a r y c y c l e si nb i p a r t i t et o u r n a m e n t sb yz s o n g ，k z h a n g ，m a n o u s s a k i s ， a n dj w a n g ， 2 0 0 4 ，v o l k m a n nc o n f i r m e dt h a te a c hr e g u l a rm u l t i p a r t i t et o u r n a m e n t i sc y c l ec o m p l e m e n t a r y , u n l e s si t i sam e m b e ro fa 缸i t ef a m i l yo fr e g u l a rm u l t i p a r t i t s t o u r n a m e n t s h o w e v e r ，t h ep r o b l e ma b o u tt h ee x i s t e n c eo fc o m p l e m e n t a r yc y c l e si n m u l t i p a r t i t ed i 鲈a p h sw h i c ha r en e i t h e rt o u r n a m e n t sa n db i p a r t i t et o u r n a m e n t sn o r l o c a l l ys e m i c o m p l e t ed i g r a p h sa n dr e g u l a rd i g r a p h si ss t i l lo p e n i ts e e m st ob eq u l t e l y d i f f i c u l t s o ，w eg i v en e wt h ed e f i n i t i o no fc o m p o n e n t w i 8 ec o m p l e m e n t a r yc y c l e s a tf i r s t w h i c hi 8d e f i n e d 蹒f o l l o w s ： d e f i n i t i o nl e tm ，kb et h ep a r t i t es e t so fd i g r a p hd i ft h e r ee x i s tt w o v e r t e xd i s j o i n tc y c l e sca n d i nds u c ht h a tm n ( v ( c ) uy ( ) ) 口f b ra l li = l ，2 ，c ，t h e nca n d a r es a i dt ob eap a i ro fc o m p o n e n t w i s ec o m p l e m e n t a r yc y c l e s o f d ad i g r a p hdc o n t a i n st w oc o m p o n e n t w i s ec o m p l e m e n t a r yc y c l e s t h e ndi sc y c l e c o m p o n e n t w i s ec o m p l e m e n t a r y i nt h i st h e s i sw ew i l lm a i n l ye x a m i n et h ee x i s t e n c e so fc o m p o n e n t w i s ec o m p l e m e n - t a r yc y c l e sa n dc o m p l e m e n t a r yc y c l e si nm u l t i p a r t i t et o u r n a m e n t s i ti sd i v i d e di n t o f i v ec h a p t e r s t h et h e s i ss t a r t sw i t has h o r ti n t r o d u c t i o n i nc h a p t e r2 ，f o rt h ef i r s tt i m e ，w eg i v en e wd e f i n i t i o no fc o m p o n e n t w i s ec o r n o p l e m e n t a r yc y c l e s ，b yt h ed e f i n i t i o n ，ap a i ro fc o m p l e m e n t a r yc y c l e si sap a i ro fc o m - p o n e n t w i s ec o m p l e m e n t a r yc y c l e s ，s ot h i sd e f i n i t i o nh a si m p o r t a n ts e n s e t h es a m e v i 山东大学博士学位论文 t i m e ，f o rt h ef i r s tt i m e ，w ep r o v et h ee x 斌e n c oo fc o m p o n e n t w i s ec o m p l e m e n t a r yc y c l e s i ns o m ed b 8 s 簋o fm u l t i p a t t i r et o u r n a m e n t sa n do b t a i nt h ef o l l o w i n gi m p o r t a n tr e s u l t s ： f i r s t l y , w et r yt oe x a l n i n et h ee x i s t e n c eo fc o m p o n e n t w i s ec o m p l e m e n t a r yc y c l e si n 2 - s t r o n gm u l t i p a r t i t et o u r n a m e n t s n o t et h a te v e r y2 s t r o n gm u l t i p a r t i t et o u r n a m e n t c o n t a i n sa3 - c y c l e l e tcb ea3 - c y c l eo fm u t t i p a r t i t et o u r n a m e n td i fd y ( qi 8 s t r o n g ，t h e nd v ( c ) c o n t a i n sal o n g e s tc y c l e s u c ht h a tca n d a r et w oc o m p o - n e n t w i s ec o m p l e m e n t a r yc y c l e so fd w em a i np r o v et h e 耐e n c eo fc o m p o n e n t w i s e c o m p l e m e n t a r yc y c l e sw h e nd v ( c ) i sn o n s t r o n g ? c o n c l u s i o n1l e tdb ea 2 - s t r o n gn - p a r t i t et o u r n a m e n tt h a ti sn o tat o u r n a m e n t ， w h e r en26 ，cb ea 3 - c y c l eo fda n dd y ( b en o n s t r o n g f o rt h eu n i q u ea c y c l i c s e q u e n c ed l ，1 ) 2 ，现0 fd y ( c ) ，w h e r ea22 。i ft h e r ei so n l ys o m eo n e 历 c o n t a i n i n gc y c l e sa n dt h eo t h e r sc o n s i s to fas i n g l ev e r t e x ，w h e r e1 i 口，t h e nd c o n t a i n sa p a i ro fc o m p o n e n t w i s ec o m p l e m e n t a r yc y c l e s c o n c l u s i o n2l e tdb ea 2 - s t r o n gn - p a r t i t et o u r n a m e n tt h a ti sn o tat o u r n a m e n t ， w h e r en 6 ，ab ea 3 - c y c l eo fda n dd v ( c ) b en o n s t r o n g f o rt h eu n i q u ea c y c l i c s e q u e n c ed l ，i ) 2 ，一，i ) 口d fd 一矿( g ) ，w h e r ea 2 ，i fi 矿( d a + l 一) i = 1 ，轨c o n t a i n s c y c l e sf o ri = 1o ri = o ，a n dt h eo t h e r sc o n s i s to fas i n g l ev e r t e x ，t h e nd c o n t a i n sa p a i ro fc o m p o n e n t w i s ec o m p l e m e n t a r yc y c l e s c o n c l u s i o n3l e tdb ea 2 - s t r o n gn - p a r t i t et o u r n a m e n tt h a ti sn o ta t o u r n a m e n t w h e r e 竹6 ，口b ea3 - c y c l eo fda n dd y ( 研b en o n s t r o n g f o rt h eu n i q u ea c y e l i e s e q u e n c ed 1 ，d 2 ，玑o fd 一矿( a ) ，i fd la n d 风c o n t a i nc y c l e sa n dt h eo t h e r s c o n s i s to fas i n g l ev e r t e x ，t h e ndc o n t a i n sap a i ro fc o m p o n e n t w i s ec o m p l e m e n t a r y c y c l e s c o m b i n i n gc o n c l u s i o n1 ，c o n c l u s i o n2 ，a n dc o n c l u s i o n3 ，w eh a v et h ef o l l o w i n g c o n c l u s i o n c o n c l u s i o n4l e tdb ea2 一s t r o n gn ( n 6 ) 一p a r t i t et o u r n a m e n tt h a ti sn o ta t o u r n a m e n t ，cb ea3 - c y c l eo fda n dd v ( c ) b en o n s t r o n g f o rt h eu n i q u ea c y c l i c s e q u e n c ed i ，d 2 ，玩o fd y ( g ) ，w h e r e 口2 ，1 e td c = 皿f 皿c o n t a i n sc y c l e s ， i = 1 ，2 ，a ) a n d 珐； d 1 ，d 2 ，d a ) d c i fd c 0 a n de a c he l e m e n to f 珐 c o n s i s t so fa 8 i n g l ev e r t e x ，t h e ndc o n t a i n sap a i ro fc o m p o n e n t w i s ec o m p l e m e n t a r y c y c l e s s e c o n d l y , w ec o n f i r mt h ee x i s t e n c eo fe o m p o n e n t w i s ec o m p l e m e n t a r yc y c l e si n l o c a l l ya l m o s tr e g u l a rm u l t i p a r t i t et o u r n a m e n t sw h o s ea l lp a r t i t es e t sh a v et h es a m e e a r d i n a l i t y c o n c l u s i o n5l e tdb eal o c a l l ya l m o s tr e g u l a rc - p a r t i t e ( c 3 ) t o u r n a m e n t i 山东大学博士学位论文 祈t hl y ( d ) l 6 i fa l lp a r t i t es e t sh a v et h es a m ec a r d i n a l i t y , t h e ndc o n t a i n sap a i r o fc o m p o n e n t w i s ec o m p l e m e n t a r y c y e l ，u n l e s sd i si s o m o r p h i et o 霹，d s ，2 ( s e ef i g 1 1 ，f i g 1 3 ) l a s t l y , w ec o n s i d e rt h es p e c i a lc a s ew h e r et h ed i f a p h 8a r ea l m o s tr e g u l a r3 - p a r t i t e t o u r n a m e n t s c o n c l u s i o n6i fdb ea na l m o s tr e g u l a r3 - p a r t i t et o u m a m e n t 丽t hi y ( d ) i 6 ， t h e ndc o n t a i n sa p a i ro fc o m p o n e n t w i s ec o m p l e m e n t a r yc y c l e s ，u n l e s sd i si s o m o r p h i c t o 仍2 ，s k e t c h e di nf i g 1 3 i nt h ef o l l o w i n g ，w eo b t a i nr e s u l t so nc o m p l e m e n t a r yc y c l e sw i t hf i x e dl e n g t hi n m u l t i p a r t i t et o u r n a m e n t s i nc h a p t e r3 ，w ep a r t i a l l yp r o v et h ec o n j e c t u r eg i v e nb yy e oi n1 9 9 9a n do b t a i n t h ef o l l o w i n gc o n c l u s i o n ： c o n c l u s i o n7a r e g u l a rc - p a r t i t et o u r n a m e n tdw i t hc 5a n dl y ( d ) i 之8h a s ap a i ro fv e r t e xd i s j o i n tc y c l e so fl e n g t h5a n dl y ( d ) i 一5 1 ti sp o s s e s s e do fc e r t a i ne f f e c tf o rc o m p l e t e l ys o l v i n gy e o sc o n j e c t u r e i nc h a p t e r4 ，f o rt h ef i r s tt i m e ，w ee x t e n dt h ep r o b l e mo fc o m p l e m e n t a r yc y c l e s o fr e g u l a rm u l t i p a r t i t et o u r n a m e n t st om u l t i p a r t i t et o u r n a m e n t sw h i c ha r en o tr e g u l a r a n do b t a i nai m p o r t a n tr e s u l tb yw h i c hw ec a ng e tal o to fi m p o r t a n tr e s u l t s c o n c l u s i o n8l e tdb eal o c a l l ya l m o s tr e g u l a rc - p a r t i t e ( c 3 ) t o u r n a m e n t w i t hi y ( d ) i 6 i fk ，一，ka r e t h ep a r t i t es e t so f da n di k l = i i _ = j k i ， t h e ndc o n t a i n sa p a i ro fv e r t e xd i s j o i n tc y d e so fl e n g t h3a n di y ( d ) i 一3 ，u n l e s sd i s am e m b e ro faf i n i t ef a m i l yo fm u l t i a r t i t et o u r n a m e n t s t h i sr e s e tl e a d st oc o n c l u s i o n5a n dt h en e x tc o r o l l a r i e sh o l ds i n c ee v e r yr e g u - l a rm u i t i p a r t i t et o u r n a m e n ti sal o c a l l ya l m o s tr e g u l a rm u l t i p a r t i t et o u r n a m e n tw h o s e p a r t i t es e t sh a v et h es a m ec a r d m a l i t y 、 c o r o l l a r yl ( v o l k m a n n 1 6 ) hd i sar e g u l a r3 - p a r t i t et o u r n a m e n tw i t hi y ( d ) i 6 ，t h e ndc o n t a i n sap a i ro fv e r t e xd i s j o i n tc y c l e so fl e n g t h3a n di y ( d ) | _ 3 ，u n l e s sd i si s o m o r p h i ct od a 2 ( 8 e ef i g 1 3 ) c o r o l l a r y2 ( v o l k m a n n 1 5 1 ) i fd i sa r e g u l a rc - p a r t i t e ( c 4 ) t o u r n a m e n tw i t h l y ( d ) i 6 ，t h e nd c o n t a i n sap a i ro fv e r t e xd i s j o i n tc y c l e so fl e n g t h3a n di y ( d ) i 一3 ， u n l e s sdi si s o m o r p h i ct o 霹，d 4 ，2 ，域2 ( s e ef i g 1 1 ，f i g 1 4 ，f i g 1 5 ) t h e8 a m et i m e w ee x t e n dy e o sc o n j e c t u r et oag e n e r a le a s ea n do b t a i nt w on e w c o n j e c t u r e s c o j e c t u r el e tdb eal o c a l l ya