（基础数学专业论文）包含大圈的2因子在二分图中的存在性.pdf

摘要 本文研究了二分图中包含大圈的2 一因子存在的充分条件，得出 了以下结论 ( 1 ) 设g a 帆，k ；e ) 是一个二分图，满足暇i 。眈j n 曲+ 1 ， 其中 s 苫4 ，k 芑1 是两个正整数定义 o l ( g ) = m i n e ( u ，g ) + d o ，g ) ：“，y 矿( g ) ，u v 圣e ( g ) ) 如果 c r z ( g ) 苫z ( 1 _ ；) n 1 + 2 ，则g 有一个z 因子包含t 个长至少为知的 点不交的圈 ( 2 ) 设g ；似，吒；e ) 是一个二分图，满足k f = 畦f = 肛2 始，其中 k , s , n 为三个正整数且七2 ，s 之4 ，如果q j ( g ) 三2 | ( 1 一形加+ 七1 ， 那么对g 的任意七条独立边e t ，e ”g 有一允包含女个点不交的 ； 圈c l ，e 的2 - 因子，使得吃( c f ) ，上t l c , l 2 s 关键词：均衡二分图：圈；大圈；2 - 因子；给定边 a b s t r a c t i nt h i s p a p e r ，w es t u d yt h es u f f i c i e n tc o n d i t i o n s o fe x i s t e n c eo f 2 - f a c t o r sc o n t a i n i n gl a r g ec y c l e si nb i p a r t i t eg r a p h s t h em a i nr e s u l t sa r e g i v e na sf o l l o w s ( 1 ) l e tg 一，；) b ea b i p a r t i t e g r a p h w i t h 暇l t 眈f = n 之站+ 1 ， w h e r es24a n dk21a r et w oi n t e g e r s w ed e f i n et h em i n i m u m d e g r e e s a mo f n o n a d j a c e n t r e , i c e so f g r a p h gt o b e 吒( g ) ，m i n a ( u ，g ) + d p ，g ) ：“，v e v ( g ) ，u v q l e ( g ) 】 i f 畎g ，z z f ( 1 - 圳+ 2 岫gh 一2 - f a c t o r w j ! t he 攀t ，七 v e a e x d i s j o i n tc y c l e so fl e n g t ha t1 e a s t2 s 。 ( 2 ) l e tg = 以，；e ) b eab i p a r t i t e g r a p h w i t h l v 。 = 阮l = m 如，w h e r e k - ；2 ，s 4 ，n b et h r e e i n t e g e r s ，i f a , ，( g ) ；2 f ( 1 一形) ，l + t 1 ，t h e n f o r a n yi n d e p e n d e n te d g e se1 ，ek ，gc o n t a i n sa2 - f a c t o rw i t hkc y c l e s c l ，一c ks u c h t h 。a te ie e ( c i ) a n d 吲2 s k e y w o r d s ：b a l a n c e db i p a r t i t eg r a p h s ；c y c l e s ；l a r g ec y c l e s ；2 - f a c t o r s ；s p e c i a le d g e s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得或其他教育机构的学位或证书而使用过的材料与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意 警位做作者够引凉签字魄如7 年月7 | h 学位论文版权使用授权书 本学位论文作者完全了解江西师范大学研究生院有关保留、使用 学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅本人授权江西师范大学研究生院 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：参 增、 签字日期：沙7 年上月2 1 7 日 包含大圈的2 一因子在二分图中的存在性 1 1 预备知识 第一章引言与预备知识 本文仅考虑有限无向简单图设g = ，e ) 是一个图，g 的顶点数 l g l - i v ( o ) l ，边数为旧( g ) 卜设x 为g 中的一个点，用心o ) 表示在g 中与工相 邻的点集，如o ) 一1 。o ) f 表示z 在g 中的度设日是g 的一个子图，s 是y ( g ) 的 一个子集， 我们记s 的导出子图为c s 1 ，定义 g - s - o v ( c ) - s ，g h - g 少r g ) 一吖h 月设石e v ( g ) - v ( h ) ，我们记 n n i n 6 n v ( c ) ，用d ( x , h ) - i n f _ x ) l 表示x 在日中的度，d r 置_ s ) 表示石在 o s 中的度，g 的最小度用6 ( g ) 表示，记g 的两个不相邻点的最小度和为 盯z ( g ) i m i n d o ，g ) + d o , ，g ) ：工e g ，y e g ，x y 岳e ( g ) ) 对于二分图g 一似，k ；e ) ，定义 j 6 “( g ) 一m i n 埘x ，g ) + c l ( y ，g ) ：工k ，y 吒) 和 o l - i g ) i m i n f d ( x , g ) + d y ，g ) ：x 影y e y z ，x y q e ( o ) g 的一些子图称为是相互独立的或点不交的，如果这些子图中任意两个子 图没有公共顶点g 的一个哈密顿圈是一个包含g 的所有顶点的圈，g 的一个 2 因子是g 的一个2 一正则生成子图，易见2 因子的每个分支是一个圈，一个哈 密顿圈是一个只有一个分支的2 一因子 设c 为图g 中的一个圈，我们用吖c j 表示圈c 的长，即圈c 中顶点的个 数圈c 称为大圈，如果f f c ) 2 2 s ，其中5 了为一个给定的常数 设g 一以，；) 是一个二分图，f = 乜，e a 为k 条独立边的集合，e l t 咒， 其中t k ，y 。k ，l s k ，j 苫3 且d ( g ) o l y , ，则g 包含七个长度为 s 的圈 考虑圈通过给定的边的情形，h w a n 一8 】做了如下猜想 猜想1 0 设七22 是。个正整数，n o ) 是一个和七相关的正整数函数，如果图 g 满足条件】g i nz 以。 ) ，盯：( g ) 厅+ 2 k 一2 ，则对g 的任意k 条独立边 。，气，g 有七个点不交的圈c i ，q ，使得 ( 1 ) 矿( c 1 ) u v ( c ：) y ( c 。) ，y ( g ) ( 2 ) e f e ( c f ) ，1 s i k y o s h i m ie g a w ae ta l 【9 】证明了这个猜想的正确性 定理1 1 设图g 的阶为n ，2 s ks ，e l ，叩。是g 的t 条独立边，如果当七量 帅c 叫扣叱孰阶学1 _ 1 ，婀g 的能条独 立边p ，气，g 有七个点不交的圈c 1 ，q ，使得q e ( c d 且睦l s 4 ，1 s f 主七 定理1 2 设图g 的阶为n ，2 ks ，e ，靠是g 的t 条独立边，如果当 s 时，盯：( g ) n + 强一2 ；当七= 形时，仃：( g ) z 悟j + 4 七一2 ，则对g 的任 3 包含大圈的2 一因子在二分i 璺| 中的存在性 意k 条独立边q ，q ，g 有七个点不交的圈c l ，c t ，使得p 。e ( e ) 且忆is 4 1 s f k 当圈的长度大于6 时，问题还有待于解决 以上我们介绍了一些在一般图中的研究成果，下面，我们将介绍在二分图中 对相似问题的研究。在下文中，图g ，以，v ：e ) 总表示均衡二分图，满足 k l 一眈l = 厅 1 9 6 2 年，m o o n 和m o s e r l l 0 】证明d i r a c 1 】和o r e l 2 1 关于哈密顿圈存在的条件可 以推广到二分图中，且有下面结论 定理1 3 设图g ；以，v ：e ) 满足厅2 ，0 1 。( g ) ，l + 1 ，则g 有一个哈密顿 圈 此后，hw a n g 证明了下列结果 定理1 4 1 1 1 设图g = ，k ；e ) 是一个二分图，满足畎l 一阢i 一，i ，2 k ，如果 6 ( g ) 芑k + 1 ，则g 包含七个独立的圈 。 ： 定理1 5 1 习设图g 一以，k ；e ) 是一个二分图，满足畋【a 眈1 一n ，2 k ，如果 6 ( g ：l z 要+ 1 ，则g 有一个恰好包含七个独立的圈2 - 因子 x i a n gw e nl i 【1 3 l 等将hw a n g 的条件推广，得出了下面的结论 定理1 6 设图g - g ，；e ) 是一个二分图，满足暇i 一眈卜撑，2 k ，如果 0 2 ( g ) _ ，z + 2 ，则g 有一个恰好包含j 个独立的圈2 一因子 此外，gc h e n 1 4 1 等又证明了 定理 1 7 设图g = 形，屹；e ) 是一个二分图，满足 畎j ；畦ln 2 m a x 5 l 嬖+ h ，若6 。，( g ) 苫，l + 1 ，则g 有一个恰好包含七个独立 的圈2 因子 如果考虑圈的长度，hw a n g l l l l 做了如下的猜想 猜想1 8 殴图g = ( k ，k ；) 是个二分图，满足毗i = i l ；n ，2 k ，如果 包含大圈的2 一因子在二分图中的存在性 6 ( g ) 2 k + 1 ，则g 包含k 个独立的4 圈 同时，hw a n g 1 1 l 证明了下面结论 定理1 9 设图g 一形，k ；e ) 是一个二分图，满足阢| _ 眈i = ，l 一2 k ，如果 a ( g ) 之k + 1 ，则g 包含p 一1 个独立的4 - 圈和一条与这些圈独立的且长为4 的路 当考虑圈的长度稍大时，h w a n g 1 5 i 得出了下面的结果 定理2 0 图g = 以，；) 是一个；分图，满足畋i = 眈i = n ，s k ，sz 3 ，如 果6 ( g ) 芑o 一班+ 1 ，则g 包含k 个独立长至少为2 s 的圈 在此基础上，y hj m ，“ug u iz h e n 1 6 j 证明了下面的结果 定理2 1 图g = 形，k ；e ) 是一个二分图，满足暇i 。阢l 一，l s k ，s 之3 ，k 苫1 ， 如果6 ( g ) 乏| ( 1 一 n 1 + 1 ，则g 有一个2 - 因子恰好包含t 个独立的长至少为2 s 的圈 ， 同时，y a hj i n ，l i ug u iz h e n 1 6 】提出：定理2 1 中的最小度条件6 ( g ) 是否可以 推广为最小度和条件q 。( g ) y a nj i n 1 7 l 又证明了 、 定理2 2 图g 一以，；e ) 是一个二分图，满足n i ；忙i = 甩 s k ! 善中s 乏4 ， 七z 2 为两个正整数，如果吼- ( g ) 乏2 ( 1 一印1 + 2 ，则g 包含七个独立的长至少 为2 s 0 9 圈 我们【1 8 】在此基础上，将定理2 1 推广，证明了如下结论 定理2 3 图g 一彤，；e ) 是一个二分图，满足肛i 一畦| | ，l s k + 1 ，s 乏4 ， 七乏1 ，如果仃z ( g ) z 2 f ( 1 一 n + 2 ，则g 有一个2 因子恰好包含七个独享的长至 少为2 s 的圈 考虑圈经过定边的情况，gc h e n 等【1 9 j 证明了如下结果 包含大圈的2 一因子在二分图中的存在性 定理2 4 图g = 以，k ；e ) 是一个二分图，满足k i = 眈i 一 ，2 k ，k 乏1 ，如 a u c g 灿a x ，莩p 蝴c g m 阿，f 半肛和的任 意七条独立边q ，气，g 有七个点不交的圈c 1 ，c 。，使得巳e e ( c ；) 且l c “s6 ， 1 量f 七 gc h e n 1 9 】同时也将这个结果推广为2 - 因子的情形，得出如下结果 定理2 5 图g = 以，k ；e ) 是一个二分图，满足n i t 眈i = n ) 2 k ， k 乏2 ， 如飙c g 舯a x 莩卜蝴c g 叫半1 ，| 半p 对g 的 任意t 条独立边8 l ，气，g 有一个2 - 因子包含七个点不交的圈c l ，g ，使得 e f ( c f ) ，1 s is k 我们在前人t 作的基础上，证明了下面结果 定理2 6 刎图g = 以，k ；e ) 是一个二分图，满足k l 阢l = ，l ，s k ， k 2 ， sz 4 如果盯u ( g ) 芑2 ( 1 一形n + 七1 ，则对g 的任意七条独立边e l ，g 有_ 个 2 - 因子包含后个点不交的圈c l ，c 。，使得q 巧( c f ) 且b i z2 s ，l 玉i s k 作为定理2 6 的直接推i b 我们有 定理2 7 2 5 1 图g ，彤，；e ) 是一个二分图，满足肛l - i v , j 一，l s k ， k 苫2 ， 5 4 如果6 ( g ) 乏f ( 1 一形印+ 七1 ，则对g 的任意七条独立边p i 叩。，g 有一个2 - 因子包含t 个点不交的圈c 1 ，c i ，使得e ；e ( c i ) 且f c i f 苫2 s ，1 s i 尼 包含大圈的2 一因子在二分图中的存在性 2 1 引言 第二章包含大圈的2 一因子的度和条件 我们称均衡二分图g 一，v ：e ) 为偶哈密顿连通的，如果对任意一对点 “k ，v ，存在一条从“到v 的哈密顿路我们先介绍几个引理 引理2 1 【1 6 】设p x 1 x p 为g 的一条路，满足一k ，其中p = 2 r + d ，d - 0 或1 i 发y e v ( g ) 一y ( p ) 且y 如果d p ，尸) + d b 。，p ) 乏，+ 1 ，则g 有一条路 尸使得矿( p ) ；矿( p ) u ) ， 引理2 2 1 1 5 l 设t s 为两个正整数，c 为g 中一个长为2 t 的圈，点 g y ( c ) 如果d ( ，0 ，o + ，则c + 包含一个圈c 满足 2 s s f ( c ) s k + 1 ，使得图g 中不相邻两个点的最小度和 仃：c g ，之z f ( - 一) n 1 + 2 当七_ ，：时i 因为盯：p ，三n + z ，胛+ ，所醇 q j ( g ) z , t 7 2 ( g ) 厅+ 1 ，由定理1 3 ，g 有一个哈密顿圈下面我们假设七苫2 由 定理2 2 ，g 包含k 个长至少为2 s 的点不交的圈我们将证明以下几个断言 断言1 g 包含k 个点不交的圈c 一，c 。，每个圈的长至少为2 s ，使得 g 一矿( u ：；c 。) 包含一条哈密顿路 使得 断言1 的证明我们在g 中选取七个长至少为2 s 的点不交的圈c 1 ，c 。， z ( c r ) 是最小的 在满足( 1 ) 的前提下，我们选取c 1 ，一，c 。，使得 g y ( u 乞。c i ) 中最长的路的长度最大 ( 2 ) 设h = u , l 。c ，d = g v ( - ) 且i _ d l = 2 d 如果d = o ，定理2 3 已得证现在假 包含大圈的2 一因子在二分图中的存在性 设d z 1 令f ( c ，) 一2 ，l 札七) 显然，厅，乏s 且忍= 妻啦+ d 不失一般性， 设p = 毛石。为d 中最长的路，满足x 1 k ，p 一2 r + ，这里fz o 或1 假定 断言1 不成立，即p + d ( u ，q ) 2 厶- 1 由引理2 2 和( 1 ) ，我 r 们可得f ( c ；) n 2 s 由引理2 3 ，存在_ 个点矿( c ；) n 使得x o x l e ( g ) 且 c ，n q x o + u 包含一个长为2 s 的圈用c 。替换c i ，则我们得到d 的一条路 p 一石。x ，与( 2 ) 相矛盾，：所以p ；2 d 这就证明了断占1 ( 如图1 ) 一 r。 g ( 图1 ) g 包含大圈的2 一因子在二分图中的存在性 断言2g 有一个2 - 因子至少包含k 个圈，每个圈的长至少为2 s 断言2 的证明我们先定义s e v c 回：d 。，t f ( 一詈) 栉1 + 1 若 s ；垂，则6 c g ，乏( t 一) n 1 + ，由定理2 - ，g 有一个z - 因子包含七个圈，每个 圈的长至少为2 s 则定理2 3 得证：g s 一中i 对于s 中的任意一点，不妨假 i 受u e s n h ，对恻且，荆嘶) 苫吼( g ) ，可删v ) z ”圳+ 1 所以g 旷( s ) j 为g 的一个点或一条边此外，因为g 的最大度 ( g ) s 玎，c r ：( g ) 之z ( ，一) 席1 + z ， 则对任意工矿( g ) ， 我 f ，有 d 乏：( g ) 一( g ) 苫吾邝+ 2 一 即6 ( g ) 苫丢忍+ 2 设f 是使j ! 导g 包拿f 个点不 交的并且长至少为厶n n c 。，c ：和g 一矿( u ：。q ) 含一条哈密顿路的最大整数 ( 注意到g y 【u ：。c i ) 可能是m ) ，在满足上述条件的前提下，我们选取f 仑长 至少为2 s 的圈c 。，c ，使得f ( c r ) 尽可能大由断言1 ，f 芑七设 t ( c j ) 。2 1 if 越，f ，d t g 一矿( u ：，c i ) 显然，啦之s ，f 毡，f 候要断言 2 不成立，即d m 我们设恻一2 d ，p ，工工2 一是d 的一条哈密顿路我们 分两种情形来讨论 情形1 x l x 2 d ( a e ( g ) 由宠，( c i ) 的最大性和引理2 4 ，d ( x 。，c r ) + d o 口，c t ) s n r ，f 礼，f ) 因 此，a ( x 。，d ) + a ( x 2 d ，d ) 2 ( 1 一) ( ，l ；+ d ) + 2 一荟 ch口 c 2+d 2 一j o 2 ， + 厅 ，v 智 b ，有 一 ” 0 我 i 2 一 厶 ifs i 厅为因 包含大圈的2 一因子在二分图中的存在性 d ，。) + d o “，。) 副。一2 ) + ( z 一詈户+ 2 z 五一1 这表明d 。，d ) 之j ，或d g 2 d ，d ) 芑s 易见d 中存在一个长至少为2 s 的圈，与f 的最大性矛盾所以在这种情形下，断言2 成立 情形2 x l x 。e ( g ) 我们又分两种子情形来讨论 情形2 1 l d i ，2 ，由断言1 ，此时d 为一哈密顿圈由g 为均衡二分图， 且上面定义的集合s 所包含的顶点个数至多为2 ，所以在d 中存在两点 “kn d ，v n d ，满足h ，v 岳s ，使得d 中有一条以“，v 为端点的哈密顿路， 我们把这条路记为p 注意到d ，f ( 一；) n 1 + ，d 2 f ( t 一昙) ：1 1 - - 由 意f ( c ；j 的最大性和引理7 4 ，d ，c 。) t d p ，c ；) s ，f 乱一，f 因此， 一 d 以，d ) + d ( v ，d ) 乏2 ( 1 一) ( + d ) + 2 酗 ch_ = c 1 一；，砉nr + ( z 一手) d + j c s ， 与情形1 中的证明相似，我们可得在此情形下，断言2 成立 情形2 2 恻，2 j 由断言1 ，d 为哈密顿路我们记du v 因为6 ( g ) z 三n + 2 ，且d ，d ) 。1 ， d p ，d ) j 1 ，所以d o ，) + d ( n 日) 芑，l + 4 2 。，l + 2 。善 + 2 + 2 荟厅r + 1 于 是存在日中的某个圈e ，f f 得a ( u ，c 。) + d ( y ，e 卜行；+ 1 由引理2 4 ，g c 。u d 】 包含一个长至少为厶+ 2 的圈，与f f j ) 的最大性相矛盾这就证明了情形2 2 时，断言2 成立至此，我们完成了断言2 的证明 由断言2 ，设m 是满足m k 且使得g 有一个2 因子h 包含i n 个长至少为2 s 的圈的最小币整数取h 的这脚个圈为c l ，c 。设g 。；a v 荟”1 ， 这表明在h c 。中存在某个c f ，使得d ( u ，q ) + d p ，e ) 啦+ 1 由引理2 4 ， c v ( c ，u e ) 包含一个长至少为如的哈密顿圈所以g 有一个2 因子包含朋一1 个长至少为2 s 的点不交的圈( 如图2 ) o 、 q 图2 v o 包含大圈的2 一因子在二分图中的存在性 情形2 对所有f 乱，胁) ，g i 都是偶哈密顿连通的 不失一般性，设，l ，抖。，f 礼，胁) 。我们又分两种子情形来讨论 情形2 1 n 1t n 2 ，l 。一j 设u k ，v 为g 。的一条哈密顿路的两个端点，满足h ，v 萑s 所以 d ，f ( 一吾) ，z 1 + ，d c v ，之( 一；) ，1 1 + ，于是 d ( u , h - g - ) + d ( v ，h g ，) z2 ( 1 一! s 1 多t o l 厅r + 2 2 以t l z ( 一；) ，力心+ 2 一幻 4 2 ( 小一1 ) o 一1 ) 。 因为s 芑4 ，m 七芑2 ，我们有d ，日一g 1 ) + d ( v ，h g 1 ) 似一班+ 1 这表明在 h g l 中存在某个圈c f ，使得d ( u ，c f ) + d ( y ，c f 卜j + 1 由引理2 4 ， g 少( guc f ) 】包含一个长至少为矗的哈密顿圈所以g 有一个2 一因子包含m 一1 个长至少为2 s 的点不交的圈 情形2 2 ，1 1 之s + 1 设c 1 一x 1 ) ，1 x q y 。x l ，z l k 由g 的最小度和假设，由定理1 3 ，g 是连 通的，设c ：一4 ，6 l a , b ，a ，4 。不失一般性，由g 的连通性我们可以假设 z 。6 。e ( g ) 我们再分两种子情形来讨论 情形2 2 1 d o , l ，c 2 ) 1 或d ( 口t ，c 1 ) 2 1 如果d o , 。，c ：) 之1 ，我们可以假设y 。n ，e ( g ) ；如果d ( a 。，c 。) 1 ，则假设 口，y ，( g ) 如果y l 口，( g ) ，因为g ：是偶哈密顿连通的，所以在g ：中存在 一条从4 ；到b 。的哈密顿路p ，则o v ( c u c ：) 】包含一个哈密顿圈 y 一：y q 工。b 。p 口：y 。同理，如果n 。y ，e ( g ) ，则g 少( c 。u c z ) 也包含一个哈密 包含大圈的2 一因子在二分图中的存在性 顿圈因此，g 有一个2 因子包含i n 一1 个长至少为幻的点不交的圈( 如图3 ) 图3 情形2 2 2 d ( y ，c ：) = or d ( a i ，c 1 ) 10 因为g 。是偶哈密顿连通的对每对点“n g 。，v kn g 。，在g 。中存在 一条从“到y 的哈密顿路p 、如果存在h c 。中的某个圈c ；，使得 d ，c 。) + d o ，c ，) - n ；+ 1 ，则由引理2 4 ，c v ( c ，u c 。) 包含一个长至少为钳前 圈，所以断言3 成立我们假设对于每对点“，v 满足“kn g ，v e n g 。，有 d ( “，c ，) + d ( v ，c 。) 量，l ；，f 2 ，m 此夕 ，由6 ( g ) 芝昙，i + 2 ，d ( y 。，c ：) 毒o r a ( a 。，c 。) ；0 ，我们有 d ( y ，h g - u g z ) + d 。t ，日一g tu g ：) 苫薹+ 4 一( 行t + ，l ：) 薹，z r + 4 这表明在h g ，一g ：中，存在某个圈c ；，不妨设为c ，使得 d ( y l ，c 3 ) + d ( a i ，c 3 ) 2 _ ，1 3 + 1 ，设p + = y i x l b i 口2 6 ，口l ，由引理2 4 ，我们可得 g p ( c ，u p ) j 是哈密顿图设g i ；g 一仁。，y 。) 因为g 是偶哈密顿连通的，对 1 4 包含大圈的2 一因子在二分图中的存在性 任意点“kf lg - v f qg 0 在g l 中有一条从“n v 的哈密顿路 所以 m y q d ( u ，c ；) + d o ，c 。) s 玎j ，i e 2 , ，肌 ，我f f 有 d o ，g - ? + d o ，g - ) 2 咒+ 4 一荟厅t - n l + 4 , d ，g ：) + d p ，g i ) ，o ，一1 ) + 1 由引理2 7 ，g ：有一个哈密顿圈c 0 因为 。苫s + 1，我们得到 z ( c i ) z2 s 注意到g p ( c ，u p + ) j 是哈密顿图，因此我们可得g 有一个2 因子包 含用一1 个长至少为知的点不交的圈( 如图4 ) 至此，我们完成了断言3 的证明 图4 由以上断言，我们可得g 有一个2 因子包含k 个长至少为厶的点不交的 圈定理2 3 得证 包含大圈的2 一因子在二分图中的存在性 第三章包含经过给定边的大圈的2 一因子的度和条件 3 1引言 对圈c 取定一个方向芒，设u ，v 为c 中的点，用“0 v 表示圈c 中在方向芒上 以“为起点，v 为终点的路 引理3 1 设t ，j 为两个正整数且t j 4 ，c 为图g 中一个长为五的圈，x 为 g y ( c ) 中的一个点，e e e ( c ) 为一条给定的边若d o ，c ) z j ，贝, j o v ( c ) u x 】包含 一个圈c , 使得e e e ( c ) 且2 s s l ( c ) o 我 们选取这样的七一1 个容许大圈c l 9o + o q 。使得 瞻i 尽可能的小( 1 ) 设乞。t 咒e ( c i ) ，满足鼍k ，y i ，1 s isk - 1 设日为u t , - 1 v t 、- t - , f ) 的导出子 图；d g y ( ) ，i d i 一2 d ，注意到l d i = 2 s ；工= d - 以，y 。) ，l t l = 2 ；设 7 ( g ) 2 轨，1 仉k 一1 ，则n ；2s 且，l4 荟吩+ d 断言1 对任意的石，有d ( x ，e ) s ，1 i s k 一1 1 7 包含大圈的2 一因子在二分图中的存在性 证明设x 为l 中任意一点，对任意的g ，1 i k - 1 ，若t ( q ) 一2 s ， d ( x ，c j ) s 显然成立；若存在某个g ，使得f ( c f ) = 2 t 2 s 且d ( x ，c 1 ) s ，则由引 理3 1 ，g 旷( c f ) u x 】包含一个圈c + ，满足e e e ( c ) ，2 s 量l ( c ) t2 t 用c + 代替 c ，易见与( 1 ) 矛盾，故对任意的x 工，r f f d ( x ，e ) s 一 显然d ( 气，c ) ，d ( y 。，c f ) n ；，1 f k 一1 - 断言2 是双哈密顿连通的 证明若l 是完全二分图，显然成立现考虑不是光全二分圄的倩彤对 于中任意不相邻的两点口z k ，b i 哆，有d ，e ) 5 ，d ( b i ，c ) 3 ，。 l _ i 0 ，) ，t 口。e ( g ) ，口l k ，贝t y c f _ d 中存在一条哈 密顿路尸= 魄儿a 岛如果以钆一( g ) ，则易见d 中有一个对y t 容 包含大圈的2 一因子在二分图中的存在性 许的哈密顿圈，和h 中的c 1 ，q 。组成g 的一个包含k 个答许大圈的2 - 因子， 矛盾 现在考虑x k ，钆一。 不相邻的情况因为 d ( x k ，c f ) 吩，d 也圳q ) s 1 s k 且使得定理2 6 不成立的图中边数最多的图相矛盾，从而定理得 奔- 包含大圈的2 一因子在二分图中的存在性 参考文献 【1 】g d i r a c ，s o m et h e o r e mo na b s t r a c tg r a p h s 【j 】p r o c l o n d o nm a t hs o c 2 ( 1 9 5 2 ) 6 9 - 8 1 2 】o o r e ，n o t eo nh a m i l t o n i a nc i r c u i t si j a n l e lm a t hm o n t h l y6 7 ( 1 9 6 0 ) 5 5 【3 】3k c o r r a d i ，a h a j n a l ，o nt h em a x i m a ln u m b e ro fi n d e p e n d e n tc i r c u i t si ng r a p h 【j 】，a c t am a t h a c a d s c i h u n g a r ，1 4 ( 1 9 6 3 4 2 3 - 4 3 9 【4 】ej u s t e s e n ，o ni n d e p e n d e n tc i r c u i t si nf i n i t eg r a p h sa n dac o n j e c t u r eo fe r d o sa n dp o s a , 【j 】 a n n a l so fd i s c r e t em a t h4 1 ( 1 9 8 9 ) 2 9 9 - 3 0 6 【5 】s b r a n d lgc h e n ，r f a u d r e e ，r j g o u l d ，l l e s n i a k , d e g r e ec o n d i t i o n sf o r2 - f a c t o r si j j g r a p ht h e o r y2 4 ( 1 9 9 n 1 6 5 1 7 3 ， 【6 】6g a d i r a c ，o nt h em a x i m a l n u m b e ro fi n d e p e n d e n tc r c u i t si nag r a p h 【j 】，a c t am a t h a c u d s c i h u n g a r , 1 4 ( 1 9 6 3 ) 7 8 - 8 2 。 【7 】h w a n g i n d e p e n d e n tc y c l e sw i t hl i m i t e d s i z ei nag r a p h 【j 】g r a p h sc o m b 1 0 ( 1 9 9 4 ) 2 7 1 2 8 1 【8 】8h w a n g c o v e t i n gag r a p hw i t hc y c l e sp a s s i n gt h r o u g l ig i v e ne d g e s 【j 】，j g r a p ht h e o r y 2 6 ( 1 9 9 7 ) 1 0 5 1 0 9 【9 】y e g a w a , r j f a u d r e e ，e g y o f i ，y i s h i g a m i ，r h s c h e l p ，h w a n g , v e r t e x - d i s j o i n tc y c l e s c o n t a i n i n gs p e c i f i e de d g e s 【j 】g r a p h sa n dc o m b i n1 6 ( 2 0 0 0 ) 8 1 9 2 。 【1 0 】j m o o n ，m o s e r o nh a m i l t o n i a nb i p a r t i t e 黟a p h s 【j 】i s r a e ljm a t h 1 ( 1 9 6 3 ) 1 6 3 - 1 6 5 【1 1 】h w a n g o nt h em a x i m a ln u m b e ro fi n d e p e n d e n tc y c l e si nag r a p h 【j 】j c o m b i n t h e o r y s e r b6 7 ( 1 9 9 6 、1 5 2 1 6 4 【1 2 】h w a n g o n2 - f a c t o r so fb i p a r t i t eg r a p hp 】j g r a p ht h e o r y3 1 ( 1 9 9 9 ) 1 0 1 1 0 6 【1 3 】x l j ，b w e i ，ey a n g ，n o t e - ad e g r e ec o n d i t i o no f2 - f a c t o r si nb i p a r t i t eg r a p h s j 】d i s c r e t e a p p l e d m a t h1 1 3 ( 2 0 0 1 ) 3 1 1 3 1 8 【1 4 】g c h e n ，r j f a u d r e e ，r j g o u l d ，m s d a c o b s o n ，l l e s n i a k ，c y l e s i n2 - f a c t o r so fb a l a n c e d b i p a r t i t eg r a p h s j 】g r a p h sa n dc o m b i n1 6 ( 2 0 0 0 ) 6 7 踟 【1 5 】h w a n g l a r g ev e r t e x d i s j o i n tc y c l e s i nab i p a r t i t eg r a p h 【j 】，g r a p h sa n dc o m b i n 1 6 ( 2 0 0 0 ) 3 5 9 3 6 6 1 1 6 】j i ny a n ，gl i u ，o n2 - f a c t o r sw i t hl a r g ec y c l e si nab a l a n c e db i p a r t i t eg r a p h 【j 】，c h i n e s e e n g i n e e r i n gm a t h2 1 ( 2 0 0 4 ) 9 1 0 9 1 4 2 1 1 包含大圈的2 一因子在二分图中的存在性 【1 7 】j i ny a h ，l i ug u i z h e n ，an e wr e s u l t o ni n d e p e n d e n tl a r g ec y c l e si n b i p a n i t e g r a p l l s 【j 】p r o c e e d i n g so ft h ei n t c m a