（基础数学专业论文）关于多部图的一些性质研究.pdf

广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所 取得的成果和相关知识产权属广西大学所有除已注明部分外，论文中 不包含其他人已经发表过的研究成果，也不包含本人为获得其它学位而 使用过的内容。对本文的研究工作提供过重要帮助的个人和集体，均已 在论文中明确说明并致谢。 论文作者答名幽7 君 驯睥朋椰 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即； 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论 文的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、 缩印、数字化或其它复制手段保存论文；在不以赢利为目的的前提下， 学校可以公布论文的部分或全部内容 请选择发布时间： 曲即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者答名。叫君导师签 6 a 琶黾 关于多部图的一些性质研究 摘要 在图论研究中，关于某些特殊给定图的性质研究，一直都是很多学 者所关注的问题之一，而其中较多的是关于某个给定图的h a m i l t o n 性研 究目前来说，有关多部图的研究，主要是围绕其圈的性质，如h a m i l t o n 性、分解、泛圈( p a n c y c l y ) 、以及染色等问题关于特定图的h a m i l t o n 性 研究，一直都是一个热门问题众所周知，要判定任意某个特定图是否 为h a m i l t o n 图，目前来说仍然是一个较为困难的问题之一因此关于给 定图的h a m i l t o n 性研究，虽然已经有大量的成果，但却仍然没有非常理 想的结果且探索h a m i l t o n 图的实用性，仍然是图论研究中的一个重大 难题 有关图分解问题的存在性研究，已经有很多有关完全多部图( t ) 的圈分解存在性问题方面的研究也是一个比较热门的问题之一，而且目 前为止也已取得一系列的成果 因此本文主要围绕多部图的关于圈的性质以及完全多部图特定圈的 强制分解问题进行研究 首先，本文主要研究了多部图关于圈的性质，研究了部分扎一部图的 h a m i l t o n 性，路，圈的一些性质，并由此得到了n 一部图与o r e 定理相类 似的结果 其次，本文主要研究了完全几一部图( t ) 的强制分解的存在性问题， 研究了完全n 一部图( t ) 的 g ，c j ，c 2 * 卜强制分解的存在性主要得到了 当其中的j = 5 ，k = 3 和j = 4 ，k = 4 时完全佗一部图( t ) 的 g ，c j ，c 2 七) 一强 制分解存在的充分条件也是必要的 最后，本文在前一章基础之上，进一步研究了完全礼一部图的特殊类 图强制分解的存在性问题，并得到了完全佗一部图存在 尬一e ，6 4 卜强制 分解存在的充分必要条件 本文主要采用图论方法文中有关图论及代数图论的概念可参考文 献【1 ，2 ，3 ，4 】 关键词：多部图完全多部图h a m i l t o n 图分解强制分解 r e s e a r c ho fr e l a t e dp r o p e r t i e so f m u l 月i p a r t i t eg r a p h a b s t r a c t f o rag i v e ns p e c i a lg r a p h ，r e s e a c h i n gs o m eo fi t sp r o p e r t yh a sb e e nah o ti s s u e i nt h eg r a p ht h e o r y ，a n dm a n yo ft h e ma r er e l a t e dw i t ht h eh a m i l t o np r o p e r t i e s i n t h ep a s ts e v e r a ld e c a d e s ，r e s e a r c ho fm u l t i p a r t i t eg r a p hi sm a i n l ya b o u tt h ec y c l e s p r o p e r t i e s ，f o re x a m p l e ，t h ep r o p e r t yo fh a m i l t o ng r a p h ，d e c o m p o s i t i o n ，p a n c y c l y a n dc o l o r i n go fag r a p ha n ds oo n t h eh a m i l t o np r o p e r t yo fag i v e ng r a p h a l w a y s h a sb e e nav e r yh o ti s s u ei n s t u d y i n gg r a p h s a sw ek n o w ，c u r r e n t l yt oj u d g e w h e t h e ras p e c i a lg i v e ng r a p hi sah a m i l t o ng r a p ho rn o t i ss t i nad i f f i c u l t yp r o b l e m t h e r e f o r e ，a l t h o u g ht h er e s e a r c hc o n c e r n i n gt h eh a m i l t o np r o p e r t i e so fg i v e ng r a p h h a sb e e ng o tag r e a td e a lo fr e s u l t s ，b u ts t i l lh a v en ov e r yf a s c i n a t i n gr e s u l t s a n d i n v e s t i g a t et h ef u n c t i o no ft h eh a m i l t o ng r a p hi ss t i l lah a r dn u tt oc r a c k t h ee x i s t e n c eo fd e c o m p o s i t i o na b o u tag i v e ng r a p hh a sb e e nah o ti s s u ei n g r a p ht h e o r y , a n dw eh a v ea l r e a d yo b t a i n e das e r i e so fr e s u l t so i lt h em a n d a t o r y d e c o m p o s i t i o no fac o m p l e t em u l t i p a r t i t eg 亡a p h ( t ) i n t ok - c y c l e s t h e r e f o r e ，i nt h i st h e s i sw es t u d ym a i n l ya b o u tt h ep r o p e r t i e so fc y c l e sa n d t h ee x i s t e n c eo fam a n d a t o r yd e c o m p o s i t i o ni ng i v e nc y c l e so fm u l t i p a r t i t eg r a p h a tf i r s t ，w er e s e a r c ht h ep r o p e r t i e so fc y c l e si nm u l t i p a r t i t eg r a p h ，t h ep r o p e r - t i e so fh a m i l t o n p a t ha n dc y c l ei n 几一p a r tm u l t i p a r t i t eg r a p h p r o v et h en e c e s s a r y c o n d i t i o n sf o rac o m p l e t ee q u i p a r t i t em u l t i p a r t i t eg r a p hb e e nah a m i l t o ng r a p h s i m i l a rt ot h eo r et h e m e m s e c o n d l y , w em a i n l ys t u d yt h ee x i s t e n c eo fm a n d a t o r yd e c o m p o s i t i o n o fc o m - p l e t em u l t i p a r t i t eg r a p h 玩( t ) p r o v et h ee x i s t e n c e o fa ne d g e d i s j o i n td e c o m - p o s i t i o no fac o m p l e t em u l t i p a r t i t ee q u i p a r t i t eg r a p hi n t o3 一c y c l e s ，j _ c y c l e sa n d 2 k e y r i e s a n dp r o v et h en e c e s s a r ya n d s u f f i c i e n tc o n d i t i o n sf o rt h ee x i s t e n c eo f a ne d g e d i s j o i n td e c o m p o s i t i o no fac o m p l e t em u l t i p a r t i t ee q u i p a r t i t eg r a p h w h e n j e q u a l5 ，ke q u a l3a n dje q u a l4 ，ke q u a l4 f i n a l l y , o nt h ef o u n d a t i o no fc h a p t e r3 ，w er e s e a r c ht h ee x i s t e n c eo f m a n d a ， t o r yd e c o m p o s i t i o no fae q u i p a x t i t ec o m p l e t em u l t i p a r t i t eg r a p hi n t os o m ep a r t i e - u l a rg r a p h 。p r o v et h en e c e s s a r ya n ds u f f i c i e n t c o n d i t i o nf o rt h ee x i s t e n c eo fa n e d g e d i s j o i n td e c o m p o s i t i o no fac o m p l e t em u l t i p a r t i t eg r a p h ( t ) i n t o 4 一e a n da t h em e t h o du s e di nt h i st h e s i si sm a i n l yg r a p h t h e o r e l i c f o rc o n c e p t so f g r a p ht h e o r ya n da l g e b r a i cg r a p ht h e o r yw er e f e rt h e r e a dt o 【1 ，2 ，3 ，4 】 k e yw o r d s ：m u l t i p a r t i t eg r a p h s ；c o m p l e t em u l t i p a r t i t eg r a p h s ；h a m i l t o n g r a p h ；d e c o m p o s i t i o n ；m a n d a t o r yd e c o m p o s i t i o n l v 目录 摘要i a b s t r a c ti i i 第一章绪论1 1 1 基本的概念与结论1 1 2 研究背景2 1 3 主要工作3 第二章有关多部图圈的一些性质4 2 1 引言4 52 2 引理4 2 3 主要结论5 第三章关于完全多部图( 亡) 的 岛，0 ，q 七卜强制分解1 3 3 1 引言，1 3 3 2 引理1 4 3 3 主要结论1 5 第四章关于完全多部图( 亡) 的 甄一e ，a ) 一强制分解2 3 4 1 引言2 3 4 2 引理2 3 4 3 主要结论_ 2 4 参考文献 2 9 附录3 3 记号3 3 术语3 5 致谢- - 3 7 攻读学位期间发表的学术论文目录 3 8 广西大学硕士学位论文关于多部图的一些性质研究 第一章绪论 1 1基本的概念与结论 本文讨论的图指有限简单图，在没有特殊说明的情况下，都指无向 图，没有定义的符号，术语以及有关的定义，可参阅文献 1 ，2 ，3 ，4 对于给定的有限简单图r ，我们以v ( r ) 和s ( r ) 分别表示图r 的所 有顶点，以及边集合用a u t ( r ) 表示图r 的全自同构群我们称简单 图r 为佗一部图，如果存在y ( g ) 的一个礼一划分，即v ( c ) = u 翟，五，且 ，j 1 ，2 ，扎) ，都有咒n 咒= o ，使得每个x 都是独立集记这样的 n 一部图为g ( 墨，恐，k ；e ) ，特别我们称其中的( x ，恐，) 为n 一部 图的佗一划分如果几一部图g ( 蜀，恐，；e ) 中，五与x ，之间的每一 对顶点都相邻，则称图g 为完全n 一部图，这时亦可简记为卅：，m 特 别地，当完全几一部图的每个划分的顶点数都等于t ，则简记完全n 一部图 为( t ) 对一个简单图r 中顶点牡，其度数记为d ( u ) ，图r 的最大度记为( g ) ， 最小度记为6 ( g ) ，分别简记为a ，6 如果图r 中存在一个包含所有顶点的生成圈，则又称该生成圈为 h a m i l t o n 圈，此时我们称这样的图r 为h a m i l t o n 图类似的，若图 r 中存在一条生成路，就称这条路为图r 的一条h a m i l t o n 路记图r 的 一条佗个顶点的路为r ， 设r 。和r 。是任意给定的有限简单无向图，则规定r ，和r 。的笛卡尔 积r ，r ：为具有顶点集合v ( r ，) v ( r ：) 的图，满足( u ，t ) 和( u 2 ，2 ) 相邻 当且仅当u 1 = u 2 且( 1 屹) e ( r 2 ) ，或者1 = 2 且( 乱1 ，乱2 ) s ( r 1 ) 再规定 r ，和r 2 的字典式积r 1 【r 2 】为具有顶点集v ( r ，) xv ( r 2 ) 的图，满足( 1 ) 广西大学硕士学位论文关于多部图的一些性质研究 和( 礼2 ，屹) 相邻当且仅当( 乱l ，牡2 ) e ( r 1 ) ，或者让1 = t 1 2 且( 1 ， 2 ) e ( r 2 ) 一个图r 我们可称之为是自补的，如果它与其补图r 同构对于一 个图r 来说，分解指的是其边集的一个划分，即为一系列子图，而且原图 r 的每一条边属于且只属于其中某一个子图对于某一个给定的有限简单 图r ，假设日即为图r 的这样一族边不相交边集划分，而 b ，b 2 ，且) 是任意一族相互都不同构的图如果日中的每个子图都与 b ，b 2 ，岛) 中某一个图鼠同构，那么就可称原图r 的边集划分日为图r 的一个 b 。，易，b t 一分解如果其中t 仅为1 时，则简称日为图r 的一个 b 1 一分解特别的，如果任取i ( 1 i t ) ，h 中都至少存在一个子图与其 同构，这时就称日为图f 的一个 b 。，岛，b 卜强制分解 1 2研究背景 在图论研究中，有关给定图的性质研究，一直都是很多学者所关注 的问题之一，其中较多的就是关于给定图的h a m i l t o n 性研究目前来说， 有关多部图的研究，主要是围绕其圈的性质，如h a m i l t o n 性，分解、染 色、以及泛圈( p a c y c l i c ) 等问题h a m i l t o n 圈的定义，起源于英国著名的数 学家w r h a m i l t o n 所发明的十二面体上的游戏关于特定图的h a m i l t o n 性的研究，一直都是一个热门问题众所周知，要判定某一个特定图是 否为h a m i l t o n 图，目前来说仍然是一个比较困难的问题所以到目前为 止，关于特定图的h a m i l t o n 性研究，虽然已经有大量的成果，但却仍然 没有非常理想的结果且探索h a m i l t o n 图的实用性，仍然是图论中的一 个重大难题 关于多部图的圈性质的研究，目前来说并不是很多 关于给定图的分解问题，也一直都是图论研究的热门问题之一完 全图珞分解为g 的问题已经完全解决( 见文献【2 8 ，3 0 】) 完全图其实 可以看成是每部划分都为1 个顶点的完全扎一部图有关珞一，( 其中的j 为卜因子) 的圈强制分解问题，当其中的n 为偶数时，也已经解决( 见文 献【2 8 ，3 0 】) 关于特定类图的相关路的性质的研究，t a r s i ( 见文献【3 1 1 ) 在 1 9 8 3 年给出了完全图珞存在长为k 的路r 强制分解的充要条件 2 广西大学硕士学位论文 关于多部图的一些性质研究 目前来说，关于具有等部划分的完全多部图玩( t ) 或瓦的强制 分解问题，已有一些研究，主要是关于分解成较小长圈或特殊长度圈的 情况( 见【3 2 】具有任意部划分的完全多部图的较小偶数长的圈分解) ，或其 中长度为素数( 见文献 3 3 】) 或两倍素数( 见文献【3 4 】) 长圈的强制分解情 况而关于一般多部图的路性质研究还比较少，这类研究主要有完全多 部图的长至多为5 的路的研究( 见文献【3 5 ) ，刘( 见文献 3 6 ，4 7 】) 解决了 具有相等划分的完全多部图的可解圈强制分解问题，其中可解表示关于 圈的长度上的某些较强的限制n j c a v e n a g h 研究了完全三部图的g 强 制分解情况( 见文献【3 2 】) ，e j b i l l i n g t o n ，n j c a v e n a g h ，b r s m i t h 等研究了 3 一部图以及5 一部图的路和圈强制分解问题( 见文献【3 7 】) ，得到了除了每 一部的顶点数都为偶数，且具有奇数度时，特定圈的强制分解不存在， 特定路的强制分解也有较强限制e l i z a b e t h 等研究了具有每部划分都相 等且为偶数的完全四部图的圈分解问题，给出了这样的四部图存在长为 k 的圈或长为k 的路分解的充分必要条件( 见文献 17 】) 然而这几乎就是 目前所知道的针对多部图的强制分解存在性问题的仅有的一些结果 1 3主要工作 本文工作主要研究有关多部图的一些重要性质其中第一章为绪论 部分，自绪论之后，第二章主要研究了多部图的关于圈的一些性质，研究 了一部分佗一部图的h a m i l t o n 性，路，圈的一些性质，并由此得到了佗一部 图与o r e 定理相和c h v d t a l 条件等相类似的结果 第三章主要研究完全扎部图( t ) 的强制分解的存在性问题，研究 了完全礼一部图( t ) 的 g ，0 ，q 七) 强制分解的存在性主要得到了当其 中的j = 5 ，k = 3 和j = 4 ，k = 4 时完全佗一部图( t ) 的 g ，g ，q k ) 强制分 解存在的充分条件也是必要的 第四章在第三章的基础之上，主要研究了完全n 一部图的一类特殊图 的强制分解存在性问题，并得到了完全n 一部图存在 托一e ，c 4 卜强制分 解存在的充分必要条件。 3 广西大学硕士学位论文 关于多部图的一些性质研究 第二章有关多部图圈的一些性质 2 1引言 关于多部图圈性质的研究，目前来说并不是很多，在图论的研究中， 有关某些特殊给定图的性质研究，一直都是很多学者所关注的问题之一， 其中比较多的研究就是关于给定图的h a m i l t o n 性研究目前来说，有关 多部图的研究，主要是围绕其圈的性质，如h a m i l t o n 性等、分解、染色以 及泛圈( p a z y c l i c ) 等问题关于特定图的h a m i l t o n 性的研究，一直都是一 个热门问题众所周知，要判定某一个特定图是否为h a m i l t o n 图，目前 来说仍然是一个比较困难的问题 关于多部图的有关圈的性质的研究，这方面的结果较少，本文主要 讨论了多部图的有关圈的性质，初部探讨了部分凡一部图的h a m i l t o n 性， 路，圈的一些性质，并由此得到了多部图为h a m i l t o n 图的必要条件，并 研究了多部图的度数与其最长圈c ( o ) 之间的关系 2 2引理 引理2 2 1 【1 】( o r e1 9 6 0 ) u 3 的简单图g 中，若对任二不相邻的顶点 札，都有 d ( u ) + d ( u ) 则g 为h a m i l t o n 图 4 广西大学硕士学位论文关于多部图的一些性质研究 一引理2 2 2f 1 】设简单图g 为h a m i l t o n 图，则对v 的任意非空真子集s ， 有 u ( g s ) si s l 引理2 2 3 2 1 设简单连通图g 中占 警，则g 含一条长大于或等于幼的 路 证明：任取g 中一最长路p ，设其长为m ，其起点为乱，终点为反 证，假设m 2 6 1 ，根据定理2 2 1 的方法，可构造一顶点集为v ( p ) 的圈 c 但p 的顶点数为m + 1 2 6 ，因此丽非空。再由g 的连通性， 得【y ( c ) ，顶_ 】非空，从而g 中存在一边x y ，使顶点zgc ，y c 令名为 秒在c 中的相邻点，则c 一矽名与x y 一起构成g 中长为m + 1 的( z ，z ) - 路，这与g 中最长路的长为m 的假设相矛盾 口 引理2 2 4 【2 】各个顶点的度至少为警的任意正则简单图都是哈密顿 图 j a c k s o n ( 1 9 8 0 ) 引理2 2 5 【3 】( d i r a c1 9 5 2 ) u 3 的简单图g 中，若6 ；，则g 为h a m i l t o n 图 引理2 2 6 【3 】连通图g 至少有一棵生成树 2 3主要结论 定理2 3 1 设玩，n 。，为完全m 一部图，其中：几l 他 礼仇，若 每部划分的顶占、数n 1 ，佗2 ，满足： 竹1 + 竹2 + + 礼一1 ，则完全 仇一部图珞，竹。，含一条长大于或等于2 篙17 , i 的路，且为非h a m i l t o n 图 证明：在这里，我们记完全m 一部图，n ：，的顶点集划分为l k i ，其 中m = 啦，i = 1 ，2 ，仇由定理条件知，l i i k i 1 i ，从而由完 全多部图的特性，可知在完全仇一部图。m ，中， 6 = l + i l + + 1 一1 l = n 1 + n 2 + + 7 z r n 1 5 广西大学硕士学位论文关于多部图的一些性质研究 再由条件，6 = n 1 + 礼2 + + 一1 ，所以我们有： 2 ( n a + 7 1 2 + + 铊仇一1 ) r t l + n 2 + + n 。= i v i ， 因而6 1 所以在g ，中必然含有分属于几个不同部 分独立集的顶点，这里以t 。记g ，中所包含的分属于k 的顶点个数，并 取其中t j = m a x t 1 ，t 2 ，缸) 由多部图的特性知，v u l ，乱2 g 1 ，有 d ( u 1 ) + d ( u 2 ) 2 ( k 一1 ) t j ， 而冬，厶譬令岛s 警因此，我们有： d ( u 1 ) + d ( u 2 ) ( k 一1 ) m ， 与定理条件矛盾从而满足定理条件的七一部图a ( x ，凰；e ) 为连 通图 口 7 广西大学硕士学位论文关于多部图的一些性质研究 定理2 3 5 设图a ( x 1 ，x 2 ，五；e ) 为连通s 一部图，其中i x l i = l 托i = = i 兄l = m ，s 2 ，若m 为偶数，对v u ，g ，都有： d ( u ) = d ( v ) = n 则图a ( x 1 ，咒，咒；e ) 为h a m i l t o n 图 证明：用归纳法 ( i ) 当r = 2 时，设p = h 屹地+ 1 ( 当i j 时，均) 为多部图 g ( 墨，x 2 ，五；e ) 中的一条最长路，由定理条件，此时屹，均，蚝每一 点的度数都等于2 而由p 的最长性可知，的邻域n ( u ，) 及+ ，的邻域 n ( v i + ，) 均在路p 上，从而结合条件可推知，1 , 1 ，与+ ，相连，此时满足： d ( u 1 ) = d ( + 1 ) = r = 2 ， 从而路p 为一个i + 卜圈u l v 2 + 1 z ，1 又由a ( x 。，咒，x s ；e ) 连通性以及p 的极大性可推知，在以p 为顶 点的i + 卜圈之外没有其它图a ( x 1 ，x 2 ，咒；e ) 中的顶点，所以，i + 1 = 8 m ，这说明p 为h a m i l t o n 圈 ( i i ) 假设r = k 2 时结论成立，往证r = k + l 时，多部图a ( x 1 ，x 2 ，咒 ；e ) 亦为h a m i l t o n 图首先，由引理2 2 6 ，s 一部图a ( x 1 ，恐，咒；e ) 包含 了一棵生成树，记为瓦，往证多部图g ( 墨，恐，k ；e ) 之中，包含有另 一棵生成树，与生成树死不同的是此生成树的任意一顶点乱的度数 都小于或等于k 反证法若否，即有某个顶点扩，g 的度数比k 大，不妨假设。的 度为k + 1 , v 2 n ( u 1 ) ，则死一t t l l 2 可得到一个以屹为根的小树，记其所有 的顶点分别为屹，u 2 ，u 3 ，+ 1 ，然后再把其在多部图g ( 墨，恐，咒；e ) 中所对应的边一一恢复则由h 与屹相邻，且d ) = k + 1 以及多 部图的性质特点，顶点屹，u ：，+ 。之中必存在某个顶点与v ( x ) 一 l 1 ，屹，坳，u 3 ，+ 1 ) 中某些点相连，记此类边为t ，则有：死一 p 1 屹) + t 仍然是多部图g ( x ，恐，五；e ) 的一棵生成树，故而顶点。的度为k 假如还有其它的顶点的度大于或等于k + 1 ，则用类似方法可使其刚好达 到k 8 广西大学硕士学位论文 关于多鄙图的一些性质研究 故在s 一部k + 卜正则多部图g ( 蜀，恐，墨；e ) 中，只要适当的去 掉其每一个顶点的某一边，仍然能够保留生成树所对应的边这样的 边总共有删2一点= 8 ，r n 条，且这些边不属于生成树中所对应的 任一一条边，不同的任意两条边所相邻的两个顶点也不一样这样，从 s 一部图k + 卜正则图g ( x ，咒，咒；e ) 中，去掉这类边所得到的新图 g ，( x 1 ，憨，咒；e ) 为连通k 正则图 则由我们前面的假设可知g ( x 1 ，弼，咒；e ) 为h a m i l t o n 图，由证明 过程可知，新图g 7 ( x 1 ，恐，兄；e ) 为o ( x 1 ，恐，x s ；e ) 去掉警条边所 得到的从而易知，e ( x 1 ，恐，咒；e ) 也是h a m l i l t o n 图 口 推论2 3 66 m 的正则三部图e ( x 1 ，x 2 ，x 3 ；e ) ，l x l l = i x 2 l = i x 3 l = m 为哈密顿图 定理2 3 7 设v ( x ，i s , z ，e ) 为3 一部图，其中i x i = j y i = l z i = 仇，如果当 d ( u ，1 , 1 ) = 2 ，有m a x d ( u ) ，d ( ) ) m ，则g 包含了起点与终点度数都大于r n 的最长路径p ( u l ，耽) ，即d ( u 1 ) m ，d ( u z ) m 证明：构造集合m = 俐d ( u ) m ) ，在3 一部图g 中取一条使l e n d ( p ) n m i 达到尽可能大的最长路径p ( u l ，n ) ，往证p ( u ，n ) 满足定理条件 若否，可假设路p 的其中某个端点度数小于或等于m ，这里我们假 设起点m 的度小于或等于m 则因尸为最长路径，所以端点，的邻域全 都应包含于路p 之中，由d ( u 1 ) 2 ，顶点z ，在p 上有异于：的领域，设 为屹，k 3 ，d ( u l ，一1 ) = 2 ，由条件，m a x d ( v 1 ) ，d ( u k 一1 ) ) r n ，这样，找 到另一条路p ，= 。一2 1 + 1 岣，且端点度数d ( 坼) 与d ( 1 ) 都大 于m 因此我们有i e n d ( p ) nm i i e n d ( p ) nm l ，矛盾所以d ( u 1 ) m 定理 得证 定理2 3 8 如果g ( 蜀，恐，托；e ) 是2 一连通多部图，且v u ，y ( x ) ， 都有d ( u ) + d ( 扩) ( k 一1 ) m + 1 ，贝l jc ( g ) ( 七一1 ) m + 2 证明：为了证明定理，先看一个引理： 9 广西大学硕士学位论文关于多部图的一些性质研究 如果g 是2 - 连通的且d c ( u ，) = 2 包含m a x d ( u ) ，d ( ) ) ；，则c ( g ) m i n n ( g ) ，c ) 由引理，我们显然可得到定理结论 口 定理2 3 9 设多部图v ( x ，i s , z ；e ) ，其中i x i = l y i = 吲= t 为具有相 等划分的三部图，若v u ：v y ( g ) ，都有m a x d ( u ) ，d ( u ) ) t + 1 ，则g 为 h a m i l t o n - 图 证明：用反证法和极端化方法首先假设存在这样满足定理条件的非 h a m i l t o n 图g ，且i g i = 3 t ，我们取c = c l c 2 c l 为g 的最长环，其长度为 z 由定理2 3 8 ，我们可知z 2 t + 1 假设p 为g v ( c ) 中的一条最长路 径，并设路p 的长度为m ，起点为让，终点为u ，则由3 t = 礼z + m + 1 和 l 2 t + 1 可知， m t 一2 由定理2 3 7 ，我们可取g 的终点与起点的度数都大于可等于t + 1 的 最长路径p ，即在路p 中，有d ( u ) t + 1 ，d ( v ) t + 1 的最长路径p 又设 s = ( 让) ，t = g c ( ) 则由c 的极大性，知在s 中沿最长圈c 的任意两 个相继顶点8 i ，8 m 之间的距离d ( s ；，8 州) 2 ，否则，我们就可以得到另一 条圈：s ；u s m c ，比c 长，因此矛盾 因为路p 为g v ( c ) 的最长路径，所以( 乱) v ( c ) uy ( p ) ，n ( v ) v ( c ) uy ( p ) 又由c 的极大性，知s 中的任意顶点与t 中的任意顶点 之间的距离d ( s ，s j ) m + 1 ，若否，可设a s ，b t ，a ，b 沿c 的距离 d ( a ，b ) i 或 d 2 m + 1 一t 2 m + 1 一i ，则g = ( x 1 ，x 2 ，x 3 ；e ) 为h a m i l t o n 图 证明：将g 中的不同划分之间不相邻且度数之和大于或等于2 m + 1 的顶点对用新边连接起来，这样构作新图g 7 ，则由推论2 3 1 0 可知，添加 此类新边的过程不会减少度序列中每个元素的值又因为g ，是h a m i l t o n 图可推出未添加新边之前的图g 亦为h a m i l t o n 图，因此，这里只需要证 明g = g ，时的情形此时我们往证，满足定理条件的3 一图g 蕴含了 g = m 仇的情形 这里，我们只需往证：如果g = g 7 不是完全三部图，则可找到某个 小于或等于仇的i 值，使其不符合定理中的条件即至少存在i 个顶点， 它们的度数不超过i ，而且至少存在2 m + 1 一i 个顶点，宜它们的的度数 也小于2 m + 1 一i 由假设，如果g 不是完全3 一图，我们不妨从不同划分的不相邻顶点 对之中，选取一对，使其度数之和最大在g 7 中，顶点对u 与z ，不相邻 包含了条件d ( u ) + d ( v ) 2 m + l ，假设其中的d ( u ) d ( ) 因为我们又有 d ( u ) + d ( v ) 2 m + 1 ，因此可假设其中的d ( u ) m ，并取i 即为d ( 缸) 根据命题，我们首先要从图g 中找到i 个度数小于或等于z 的顶点i 个不妨设u x 1 ，x 2 ，因为乱，为不同划分之间不相邻顶点对中度数 之和最大的一对因此，x 。u 弱中其它与不相邻的顶点之中度数小于 等于d ( u ) ，而由前面的假设，i = d ( 让) 在g ，中总共具有2 m - d ( v ) 个此类顶 点又因为d ( 乱) 与d ( z ，) 之和最多为2 m ，因此，我们有2 m d ( y ) d ( u ) = t 再此，这里仍还需要再找到2 m + 1 一t 个度数小于2 m + 1 一i 的顶点， 由条件可知，恐u 托中与牡非邻接的顶点之中，度数均小于或等于d ( ) 由d ( u ) + d ( v ) 2 m + 1 ，我们有d ( ) 2 m + 1 一d ( u ) 在g 中，共包含了 2 m d ( u ) 个这样的顶点最后，因d ( u ) 小于或等于d ( ) ，度数小于或等于 d ( v ) 的顶点总共就有2 m + 1 一 个，这样我们就得到了2 m + 1 一i 个度小 于2 m + 1 一t 的顶点 广西大学硕士学位论文关于多部图的一些性质研究 至此，我们已经找到了这样的i ，同时又证明了d 1 i 或d 2 m + l i 2 m + 1 一i ，与假设矛盾定理得证 定理2 3 1 2 设g ( x 1 ，恐，x 3 ；e ) ，( i x l l = i 恐l = i x 3 l = m ) 为具有相等划 分的三部图，设g 的顶点度序列为d ，d 。s d 。m ，如果对于任意 i 仇+ 1 有盔i 或d 2 仇+ 1 一i 2 m i ，那么g 含有h a m i l t o n 路 证明：首先，添加一个新顶点到g 中，并与g 的每个顶点相边接，即 新图g ，= gvk 1 ，则i g 7 l = 3 m + 1 ，再假设新图g 7 的度序列为西，则 如果g ，含有h a m i l t o n 圈，则可将由于将g 7 之中后添加的新顶点去掉， 即可得到原3 一部图g 的一条h a m i l t o n 路，因此往g 7 含有h a m i l t o n 圈即 可 g 中每一个顶点都与新添加的顶点相连，所以易知，的度等于礼 且有= 由+ 1 ，( j i 或近。+ 1 一t = d 2 m + 卜i + l 2 m + 1 一i 从而由定理2 3 1 1 可知，故而添加新顶点的图g 之中含有h a m i l t o n 圈， 由前面的分析可推知，3 一图g ( x l ，恐，x 3 ；e ) 含有h a m i l t o n 路 口 1 2 3 1引言 关于给定图的分解问题，也一直都是图论研究的热门问题关于这 方面的结果主要有：完全图珞的g 一分解问题已经完全解决( 见文献 【2 8 ，3 0 1 ) 有关一，( 其中的j r 为卜因子) 的圈强制分解问题，当其中的佗 为偶数时，也已经解决( 见文献 2 8 ，3 0 】) 关于完全多部图( ) 或的强制分 解问题，当分解成较小长圈或特殊长度圈的情况( 见【3 2 具有任意部划分 的完全多部图的较小偶数长的圈分解) ，或其中长度为素数(