（应用数学专业论文）半无爪图的hamilton性质.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名：如i 缸霞 导师签字： 学位论文版权使用授权书 一、兰 21 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂 撞一可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：知承窟 导师签字：形c 。象 签字日期：2 0 06 年月c o 日签字日期：2 0 0 年阳。日 山东师范大学硕士学位论文 半无爪图的h a m ii t o n 性质 孑l 淑霞 ( 德州学院数学系，山东德州2 5 3 0 2 3 ) 摘要 h a m i l t o n 问题是图论研究的基本问题之一，1 8 5 7 年爱尔兰数学家h a m i l t o n 提出这样一个问题：“一个连通图是t t a m i l t o n 图的充要条件是什么? ”这个问题 至今尚未解决，后来人们发现它是一个n p c 问题，于是对它降低要求，间接研究 该问题一种思路是研究h a m i l t o n 图的充分条件，另一种思路是研究特殊的图 类，如：正则图，t 一坚韧图，无爪图，半无爪图等 关于无爪图的h a m i l t o n 性质，近几十年来，许多数学学者致力于它的研究， 并且得到了很多优美的结论a i n o u c h e 在文献 2 中首先引进半无爪图的定义， 半无爪图是包含无爪图的更大的图类，a i n o u c h e 在文献 2 中将无爪图的一些结 果，特别是关于h a m i l t o n 性质的，推广到半无爪图本文将无爪图的另外的一 些结果推广至半无爪图时也成立这样，这些性质可以应用到更大的图类上 本文仅讨论有限、无向、简单图，设g 是一个图，y ( g ) 和e ( g ) 分别表示g 的顶点集和边集对任意v e v ( g ) ，n ( v ) 表示点v 在g 中的邻点集， n v l = ( v ) u v ) 设g 是连通图，对于“，v 矿( g ) ，d ( u ，v ) 表示，v 之间的最短 路长，称为，v 的距离若g 中无同构与墨，的导出子图，则称g 是无爪图如 果任意z ，y v ( a ) ，d ( x ，y ) = 2 ，都存在u ( x ) n ( y ) ， 使得 ( “) n ( x ) u n ( y ) ，则称g 是半无爪图显然，半无爪图是包含无爪图的更大 的图类 在第一章预备知识中介绍了半无爪图h a m i l t o n 性质的研究现状及本文涉及 到的图论的一些基本概念、基本知识和使用的有关术语、符号 关于2 一连通无爪图，有以下结果： 定理若g 是2 连通的无爪图，其阶为h ，则当h 3 5 + 2 时，g 是 l t a m i l t o n 图 山东师范大学硕士学位论文 在第二章2 一连通半无爪图的h a m i l t o n 性质中把这个结果推广至半无爪 图： 定理若g 是2 一连通的半无爪图，其阶为拧，则当h 3 6 + 2 时，g 是 h a m i l t o n 图 关于3 一连通无爪图，有以下结果： 定理“。若g 是3 一连通的无爪图，其阶为n ，则当，5 占一5 时，g 是 h a m i l t o n 图 在第三章3 一连通半无爪图的h a m i l t o n 性质中将这个结果推广至半无爪图 类，并且把玎的值提高到5 8 4 ，证明了半无爪图的以下结果： 定理若g 是3 一连通的半无爪图，其阶为n ，则当”5 8 4 时，g 是 h a m i l t o n 图 关于k 一连通半无爪图有以下结果： 定理。1 若g 是k 一连通的半无爪图( k - - 2 ) ，如果对于g 中任意基数为k + 1 的独立集x ，都有d ( v ) h k ，则g 是h a m i l t o n 图 盹j 在第四章k 一连通半无爪图的h a m i l t o n 性质中证明以下结论，它减弱了以 上定理的条件： 定理若g 是七一连通的半无爪图( k 2 ) ，如果对于g 2 中任意基数为k + l 的独立集x ，都有d ( v ) h k ，则g 是h a m i l t o n 图 v e 在第五章图的控制圈的个下界中得到以下结论，它在特定的条件下推广 了田丰在 1 9 中的结果： 定理若g 是2 一连通的非h a m i l t o n 图，含有一个控制圈c ，令 r = 矿( g ) 一联c ) ，如果存在v 矿( c ) ，使呔( v ) 2 ，则g 包含的控制圈的长至少为 2 仃一2 关键词：连通图；无爪图：半无爪图；h a m i i r o n 图 中图分类号：0 1 5 7 5 山东师范大学硕士学位论文 h a m ii t o n i c i t yo fq u a s i 。c i a w f r e eg r a p h s k o n gs h ux i a ( d e p a r t m e n to fm a t h e m a t i c s ，d e z h o uu n i v e r s i t y ，d e z h o us h a n d o n g 2 5 3 0 2 3 ，c h i n a ) a b s t r a c t h a m i l t o np r o p e r t i e sh a v eb e e nas u b j e c to fm a n ya u t h o r si nt h er e c e n t y e a r s i n1 8 5 7 ，t h ei r e l a n dm a t h e m a t i c i a n i l a m i t o nr a i s e dt h ep r o b l e m ： “i fac o n n e c t e dg r a p hish a m i l t o n i a n ，w h a ti si t sc o m p l e t ea n dn e c e s s a r y c o n d i t i o n s ? ”t ot h i sd a y ，i ti sn o tr e s o l v e da n dl a t e ri t i sf o u n dan p c p r o b l e m s op e o p l e s t u d i e di ti nt w ow a y s ：s t u d y i n gi t sc o m p l e t e c o n d i t i o n sa n ds t u d y i n gs o m es p e c i a lg r a p h s - - r e g u l a rg r a p h s ，t - t o u g h g r a p h s ，c l a w f r e eg r a p h s ，q u a s i c l a w f r e eg r a p h sa n de t c i nt h er e c e n ty e a r s ，m a n ya u t h o r s s t u d i e dt h ep r o p e r t i e so nc l a w f r e e g r a p h sa n do b t a i n e dm a n yb e a u t i f u lr e s u l t s i n 2 a i n o u c h ef i r s td e f i n e d t h e c o n c e p t o fq u a s i c l a w f r e eg r a p h s e v e r yc l a w f r e eg r a p hi s q u a s i c l a w f r e eg r a p h a n di n 2 h ee x t e n d e ds o m er e s u l t so nc l a w f r e e g r a p h st oq u a s i c l a w f r e eg r a p h s i nt h i sp a p e rw eo b t a i n e ds o m er e s u l t s o nq u a s i c l a w f r e eg r a p h s w ec o n s i d e ro n l yf i n i t eu n d i r e c t e dg r a p h sw i t h o u tl o o p s a n dm u l t i p l e e d g e s f o rt e r m i n o l o g y ，n o t a t i o na n dc o n c e p t sn o td e f i n e dh e r es e e 1 l e tg = ( 矿( g ) ，e ( g ) ) b eag r a p h ，w h e r ev ( g ) a n de ( g ) d e n o t et h ev e r t e x s e ta n de d g es e to fgr e s p e c t i v e l y i fv v ( a ) ，t h e n ( dd e n o t e st h en e i g h b o r h o o ds e to fvi ng ，a n d m 词= 肌力u f 订 f o ra n yt w od i s t i n c tv e r t i c e s “，v v ( g ) ，d ( u ，v ) d e n o t e st h ed i s t a n c e i agf r o m “a n dv ag r a p hgi sc a l l e dc l a w f r e e i fi tc o n t a i n sn oi n d u c e ds u b g r a p h 3 山东师范大学硕士学位论文 is o m o r p h i ct o k 1 、3 t h ec o n c e p to fq u a s i c l a w f r e eg r a p h sw a si n t r o d u c e db ya i n o u c h ei n 2 ag r a p hgi sc a l l e dq u a s i c l a w f r e ei fi ts a t i s f i e st h ep r o p e r t y ： d ( x ，y ) = 2 t h e r ee x i s t s “( x ) n ) s u c ht h a t 0 ) n ( x ) u n ( y ) o b v i o u s l ye v e r yc l a w f r e eg r a p hi sq u a s i c l a w f r e e g r a p h i nc h a p t e r1w ei n t r o d u c et h et e r m i n o l o g ya n dn o t a t i o no fg r a p ht h e o r y r e l e v a n tt ot h i sp a p e r f o r2 - c o n n e c t e dc l a w f r e eg r a p h s ，t h e r ee x i s t st h er e s u l t ： t h e o r e m 洲l e tgb e2 - c o n n e c t e dc l a w f r e eg r a p ho fo r d e rn ，if n 3 占+ 2 ，t h e ngi sh a m i l t o n i a n i nc h a p t e r2w ee x t e n dt h er e s u l tt oq u a s i c l a w f r e eg r a p h s t h e o r e m l e tgb e2c o n n e c t e dq u a s i c l a w f r e eg r a p ho fo r d e rn ，if s 3 6 + 2 ，t h e ngjsh a m i l t e r t i a n f o r3 一c o n n e c t e dc l a w f r e eg r a p h s ，t h e r ee x i s t st h er e s u l t ： t h e o r e m l e tgb e3 - c o n n e c t e dc l a w f r e eg r a p ho fo r d e rn ，if n 5 8 5 ，t h e ngi sh a m i l t o n i a n i nc h a p t e r 3w ee x t e n dt h er e s u l tt oq u a s i c l a w f r e eg r a p h s t h e o r e m l e tgb e3 - c o n n e c t e dq u a s i c l a w f r e eg r a p ho fo r d e rn ，i f n 5 占一4 ，t h e ngi sh a m i l t o n i a n f o rk - c o n n e c t e dc l a w f r e eg r a p h s ，t h e r ee x i s t st h er e s u l t ： t h e o r e m 叫ak - c o n n e c t e dq u a s i c l a w f r e eg r a p hg ，( k 2 2 ) i sh a m i l t o n i f d ( v ) - n k h o l d sf o re v e r yi n d e p e n d e n ts e txo fc a r d i n a l i t y ( k + 1 ) v x i ng i nc h a p t e r4w eo b t a i nt h ef o l l o w i n gr e s u l t ，i tw e a k e n st h ec o n d i t i o n o ft h ef r o n tt h e o r e m t h e o r e mak - c o n n e c t e dq u a s i c l a w f r e eg r a p hg ，( k 2 ) i sh a m i l t o n i f d ( v ) 竹一k h o l d sf o re v e r yi n d e p e n d e n ts e txo fc a r d i n a l i t y ( k + 1 ) 4 山东师范大学硕士学位论文 i ng 2 i nc h a p t e r5w eo b t a i nt h ef o ll o w i n gr e s u l t ，i te x t e n d st h er e s u l to f t i a nf e n gin 1 9 i ns o m eg i v e nc o n d i t i o n s t h e o r e mi fgi s2 - c o n n e c t e dn o l ll t a m i l t o na n dc o n t a i n sad o mjn a t i n g c y c l ew i t hav e r t e xv 矿( c ) ，s u c ht h a td r ( v ) - - 2 ，w h e r er = v ( g ) 一矿( c ) f o r a 1 1d o m i n a t i n gc y c l ec t h e ngc o n t a i r sad o m i n a t i n gc y c l eo fl e n g t ha t l e a s t2 口一2 k e yw o r d s ：c o n n e c t e dg r a p h s ：c l a w f r e eg r a p h s ：q u a si - c l a w f r e eg r a p h s h a m i i t o ng r a p h s c i a s s j f i c a t i o r l ：0 1 5 7 5 5 山东师范大学硕士学位论文 第一章预备知识 在本章中先介绍半无爪图的研究现状，然后介绍论文中所涉及到的图论的 一些基本概念、基本知识和使用的有关术语、符号 1 1 研究现状 h a m i i 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 性质 关于无爪图的h a m ii r o n 性质，近几十年来，中外许多数学学者致力于它的 研究，并且得到了很多优美的结论d i s c r e t em a t h e m a t i c s 杂志在1 9 9 7 年曾给 出一个综述：c l a w f r e eg r a p h s - - as u r v e y 1 9 9 8 年，a i n o u c h e 在文献 2 中首先引进半无爪图的定义，从定义得知，半 无爪图是包含无爪图的更大的图类，同时a i n o u c h e 在文献 2 中将无爪图的一些 结果，特别是关于h a m i l t o n 性质的，推广到半无爪图在这之后，陆续有一些 数学研究者将无爪图的性质推广至半无爪图类 在本文中，作者将无爪图的另外的一些结果推广至半无爪图时也成立这样， 这些性质可以应用到更大的图类上，拓宽了应用范围 1 2 预备知识 本文仅讨论有限、无向、简单图，所使用的记号和术语约定如下，其中未加 说明的部分请参照文献 1 设g = ( y ( g ) ，e ( g ) ) 是一个图，v ( g ) 和e ( g ) 分别表示g 的顶点集和边集g 的项点的个数即g 的阶用刀表示g 的h a m i l t o n 圈是指包含g 的每个顶点的圈， 一个图若包含h a m i l t o n 圈，则称这个图是h a m i l t o n 图 设g = ( y ( g ) ，e ( g ) ) 是一个图，s 是g 的一个非空子集，以s 为顶点集，以 两端点均在s 中的边的全体为边集所组成的子图，称为g 的由s 导出的子图，记 6 山东师范大学硕士学位论文 为g s 】，g s 】称为g 的导出子图 对任意v e 矿( g ) ，用d ( v ) 表示该顶点的度，用万表示图g 的最小度( v ) 表 示点v 在g 中的邻点集，【v 一( v ) u v ) 设s 曼h g ) ， 杖v ) = ( v ) c 、s 设g 是连通图，对于群，v h g ) ，d ( u ，v ) 表示群，v 的距离，即“，v 两点闻的 最短路长若a ，b v ( g ) ，并且d ( 口，6 ) = 2 ，记 j ( a ，6 ) = 扣n ( a ) n ( 6 ) l 阻】【a u n b 】 一个图称为无爪图是指它没有同。同构的导出子图 半无爪图的概念是h i n o u c h e 在文献 2 中首先引进的，一个图g 称为半无爪 图是指图g 满足性质：对于任意x , y y ( g ) ，d 协奶= 2 ，存在点掰n ( x ) m n ( y ) ， 使得n ( u ) n o ) u ( y ) ，即a ( x ，y ) 显然，半无爪图是包含无爪图的更大 的图类 山东师范大学硕士学位论文 第二章2 一连通半无爪图的h a m ii t o n 性质 在本章中先介绍2 一连通半无爪图的一个主要结果，然后引进、证明几个有 关的引理和论断，最后证明本章的主要结论 2 1主要结果 关于无爪图，有以下结果： 定理1 3 若g 是2 一连通的无爪图，其阶为h ，则当一3 6 + 2 时，g 是 h a m i l t o n 图 本文将这个结果推广至半无爪图类 定理2若g 是2 一连通的半无爪图，其阶为h ，则当n 3 6 + 2 时，g 是 h a m i l t o n 图 2 2 几个有关的引理和论断 先引进下列记号： 斗 设g 是2 一连通图，c 是g 的一个圈，令c 表示给定方向的圈，对于v h c ) ， v 十，矿分别表示圈c 上v 的后继顶点和前继顶点，v ”，v 一分别表示圈c 上v 的第 二个后继顶点和第二个前继顶点对于u ，v 联c ) ，“cv = “矿v - v ， “c v = u l , l 一一v + v 引理1 “若g 是2 一连通的半无爪非l t a m i l t o n 图，其阶为n ，c 是g 的一个 最长圈，设日是g 【h g ) h c ) 】的一个连通分支，并且 0 ( h ) = d l ，鸸，哦) ， d l ，破，嚷在圈c 上按已排列，一点“ec f = c 融+ ，吐。- 】称为插点，如果存在 v ，v + v ( c ) 一y ( e ) ，使w ，z n 广e 贝4 ( 1 ) 存在非插点z ，e c ，1 i 兰k ，并且( 4 ) n 矿( ) = 妒 ( 2 ) j = 知，毛z a 是基数为l n , ，( h ) l + 1 的独立集，并且对于任意一对相异 点，0 ，有( z i ) n ( z ，) = 妒，z o 是h 邱的任一点 引理2 ”1设图g 的阶为n ，如果对于g 中任意两个不相邻顶点，y g ， 都有d ( x ) + d ( y ) n + l ，则g 是h a m i l t o n 连通的 引理3 若g 是2 一连通的半无爪非h a m i l t o n 图，其阶为一，c 是g 的一个 山东师范大学硕士学位论文 最长圈，是g h g ) 一h o 】的一个连通分支，“e 矿( c ) ，若“在h 中有邻点，则 “+ “一e 证明令c = v i v 2 1 j r v i ( f n ) 是g 的最长圈，任取点x 矿( h ) ，且硼e ， 下证叶v 2 e 用反证法，假设v ，v 2 仨e ，显然x v ：，x v ，仨e ，否则得到长为r + l 的圈，所以 a ( x ，v 2 ) 2 2 任取一点y j ( x ，v 2 ) ，显然y v 1 ，否则，由g 是半无爪图知”l 的邻点v r 与 v 2 相邻如果y = v ，2 3 ，所以v 3 v ，因为a ( y ，v 3 ) 2 2 ，取w j ( y ，屹) ，假设 w = _ ，j 3 ，l 茎茎，若 ， 4 ，5 ，一l ，则“n ( y ) u n ( v 3 ) ，通过y 将得到 更长的圈，矛盾 若v ，= v 2 ，则v l n ( y ) k a n ( v 3 ) ，因为y v l 正e ，得至 j v i v 3 e ，但是v ，硼屹q 是长为一l 的圈，矛盾，所以v i 仨j ( y ，v 3 ) 进一步可得v r 仨j ( y ，匕) 因此只需考虑情况t ，n ，力 v - v ( c ) ，假定肥，因为z n ( y ) n n ( v 3 ) ，得 y z e ，但是v , z y v 2 c v , 是长为r + 1 的圈，矛盾 假定w 可，因为w j ( y ，v 3 ) ，有玛e ，得hf t n ( y ) u ( b ) ，但是 朋，v l v 3 萑e 因此w 岳矿( c ) ，并且w 异于x ，y ，z 因为y j ( x ，v 2 ) ，得到w n ( x ) u n ( v 2 ) ，显然，”v 2 芒e ，所以w e ，但 v l x w v 3 c v 。是长为r + 1 的圈，矛盾 到( a v r v 2 e ，这个引理得到了证明 设g 是2 一连通的半无爪图，其阶为n ，并且n 3 j + 2 ，若g 不是h a m i l t o n 图，令c 是g 的一个最长圈，日是g 【硬g ) 一坎c ) 】的一个连通分支 论断1 l ( ，( h ) i = 2 证明由于g 是2 - 连通的，所以i ( h ) i 2 如果i r ( 日) l 2 ，由引理1 9 山东师范大学硕士学位论文 知存在一个基数为i ( ( h ) l + 1 的独立集，满足：任意一对相异点x ，y ，有 ( x ) n ( y ) = 庐，所以d ( v ) ”一( i f ( h ) 卜1 ) ，l 习 b g 的最小度为万， v e ， 所以d ( v ) d 0 ( ( h ) 卜1 ) ，代入上式得， v e ， a ( 1 n , ( h ) 卜1 ) 一i ( ( h ) 卜l ，n 3 6 + 3 ，矛盾 因此，l ( ( 日) | _ 2 ，令i ( ( h ) i = ，勺) ( f 4 5 + 2 ，又因为g 是2 - 连通 的，所以占2 ，”4 3 + 2 = 3 5 + 4 + j 一2 3 6 + 4 ，矛盾 从而h 是l | a m i l t o n 连通的 对于任意两个相异点“，v 矿( 日) ，用u h v 表示“和v 在h 中的h a m i l t o n 路 山东师范大学硕士学位论文 i l ! t t i5 ( 1 ) 已【c ，“，巳一i - t v ( h ) i ( 2 ) 己【o “，q 】- i v ( h ) i 证明：( 1 ) 如果已k ”，勺一】 4 i v ( h ) i + 62 ( 4 6 - 4 ) + 6 _ 4 8 + 2 3 8 + 4 ，矛盾 所以， g h g ) 一h c ) 】只有一个分支h 2 3 定理的证明 证明用反证法若g 是2 一连通的半无爪图，其阶为n ，当月3 6 + 2 时，g 是非h a m i l t o n 图，令c 是g 的一个最长圈，由论断6 知g 【h g ) 一h c ) 】的连通分 支只有一个h ，由论断4 知h 是h a m i l t o n 连通的，设i n c ( h ) l = c f ，c j ( i - i v ( m l + i 已【c ”，q 一】i + i 己【o ”，q 一】i + t ，q 一，c f + ，c j ，q ，勺+ - - 3 i v ( h ) t + 6 ( 3 6 - 3 ) + 6 3 占+ 3 ，矛盾 山东师范大学硕：e 学位论文 第三章3 一连通半无爪图的h a miit o n 性质 在本章中先介绍3 一连通半无爪图的一个主要结果，然后引进、证明几个有 关的引理和论断，最后证明本章的主要结论 3 1 主要结果 关于3 一连通无爪图，有以下结果： 定理1 若g 是3 一连通的无爪图，其阶为1 7 ，则当月5 6 5 时，g 是 h a m i l t o n 图 本文将这个结果推广至半无爪图类，并且把，7 的值提高到5 占一4 定理2 若g 是3 连通的半无爪图，其阶为拧，则当聍蔓5 8 4 时，g 是 h a r n i i t o n 图 3 2 几个有关的引理和论断 设g 是3 一连通图，c 是g 的一个圈，令c 表示给定方向的圈，对于v 珂c ) ， v + ，v _ 分别表示圈c 上v 的后继顶点和前继顶点，v ”，v 一分别表示圈c 上v 的第 二个后继顶点和第二个前继顶点对于u ，v 坎c ) ，“cv = “+ v - v ， u c v 。“一v + v 引理1 【2 】若g 是2 一连通的半无爪非h a m i l t o n 图，其阶为n ，c 是g 的一个 最长圈，日是g v ( g ) 矿( c ) 】的一个连通分支，“v ( c ) ，若“在h 中有邻点， 贝目“+ ”e 引理2 “1 若g 是2 一连通的半无爪非h a m i l t o n 图，其阶为n ，c 是g 的一 个最长圈，设是g 【矿( g ) 一矿( c ) 】的一个连通分支，则g 中存在基数为i ，( 日) 卜1 的独立集 并且对于任意一对相异点x , y ，有n ( x ) n n ( y ) = 引理3 若g 是3 一连通的非h a m i l t o n 图，其阶为，f 是g 的一个最长圈， 设是g v ( g ) 一矿( c ) 】的一个连通分支，如果h 不是h a m i i t o n 连通的，则 i y ( c ) i _ 4 6 - 5 引理4 “1 设图g 的阶为n ，如果对于g 中任意两个不相邻顶点x ，y g ， 都有a ( x ) + d ( y ) n + 1 ，则g 是h a m i l t o n 连通的 当查塑婆奎堂堡圭堂堡笙壅 设g 是3 连通的半无爪图，其阶为，并且，? 5 d 一4 ，若g 不是h a j n i l t o n 图，令c 是g 的一个最长圈， h 是g 少( g ) 一矿( c ) 】的一个连通分支 论断1 i m ( h ) i = 3 证明： 由引理2 知g 中存在一个基数为i ( 、( 日) f + 1 的独立集，满足：任意 一对相异点墨y ，有( x n ( y ) = 多，所以d ( v ) s 雄一( i n , ：( 4 ) v 0 ，因为g 的 最小度为占， 所以d ( v ) 占q ( 日) j + 1 ) ，代入上式得， 万( 1 ( ，( h ) l + 1 ) s 竹一l 。( h ) l - l ，i n , ，( h ) l s ! ! ；车 ，又因为疗5 j 一4 ， 陬) 丽4 8 - 5 = 4 一熹 3 ， 由于g 是3 一连通的，0 i 以i n c ( h ) i 3 ， 因此，j c ( 日) i _ 3 ，令l n c ( m l = k ，c ，q ) ( f ， = ， n ( g + ) n q ，q + ，c j ”，c l ，+ ，c ，” = 庐 证明： 4 3 ；- 5 + 2 6 - 3 ： 从而h 是h a m i l t o n 连通的 对于任意两个相异点“，v v ( h ) ，用 论断4 ( 1 ) 己【c + + ，o 一】l y ( h ) i ( 3 ) 已【q ”，q i - _ i v ( h ) i 6 d 一8 = 5 6 + 6 8 5 万，矛盾 u h v 表示u 和v 在h 中的h a m i i t o n 路 ( 2 ) 己+ ，c f _ - l l v ( m l 证明：( 1 ) 如果否心+ + ，c ，- - 】 - i v ( h ) l + i v ( t z , ) l + 陆+ + c i - - 】| + l 强”，c i f + | 百 q ”，c j f + 把，c i - c i + c j ，c 1 - c ，+ ，c i ，g - , c t + ) 5 1 v ( h ) + 9 f 5 6 1 0 ) + 9 5 8 1 ，矛盾 所以，g v ( g ) 一矿( c ) 】只有一个分支且 3 3 定理的证明 若g 是3 一连通的半无爪图，其阶为n ，当n 5 6 4 时，g 是非h a m i l t o n 图， 令c 是g 的一个最长圈，h 是g 【矿( g ) 一y ( c ) 】的唯一个连通分支，由论断3 知爿是h a m i l t o n 连通的，设i 。( 驯= 4 = 托，c ，c g _ 5 6 ，矛盾 这样( ( c f ) 一c tc i - c ，q ) n ( 7 ；u 五) 庐， 不妨设( ( q ) 一 r ，c i - c j ，c ，) ) n 互，令是e 在互= 已【r ，q - 】上的最后一 个邻点 论断7q c 。e 证明：若c 。= c i + ，则q c p e 假设c ，rr 则d 心一，) = 2 ，i 天| f f ；j g 是半 无爪图，所以存在点“n ( c , - ) n ( ) ，使n u g 【q l u h 】，显然 “芒矿( h ) u c ，c f ) ，所以”= c ，则c p n c , - 】u r 】，但是f p 芒n ( x ，) r 所以 6 山东师范大学硕士学位论文 c ，k 】，甚c fc p e 论断8n ( c p - ) n 疋= 庐 证明： 0 ，一) n e ，令c t n ( c p - ) n 正，则己 c ”，c f _ 】l 矿( h ) i ， 。- - l q + ，c ，- - 】眇( 日) i ，否则会分别得到更长圈x j c ，c ，+ c j 一己，c i 一己t c - c q x , h x j 和 x , c i c 。o c , c p - 瓦一c t 西一c lc t x t h x j ，因此 - i v ( h ) i + l 。+ + ，c ，- - 】1 + l 己 c 1 + + , c t 一】i + i o q + ，c ，一一】i + i 己 q + + ，q 一一】l + k i ，c i - , c ，c p c , c ；，c t ，e l - c ，c 5 l v ( h ) l + l o ( 5 占一1 0 ) + 1 0 5 5 ，矛盾 因为i ( c ，一) l 巧8 ，所以c p - 在l 己 c + ，q _ 】i 上至少有6 个邻点，设，分别 c p - 在l 西q ：，c j 一】i 上的第一个邻点和最后一个邻点，则 刁 已，i l ( o 一) 一 o ，c a + l - d 一2 + 1 = 6 1 ， 胛- l v w ) l + 障巳，q 】| + | 已【o ，c ，_ _ 】l + i q , v - + , q 一1 1 + l 萌q ”，c a 1 i 硷i ，c j - c ? ，c | ，c t - , c ? 、 - 4 1 v ( h ) i + p k ，矗】i ( 4 艿一8 ) + 一1 ) + 6 5 5 3 ，矛盾 情形2 任一个c k a ，都有( q ) 一( 瓴+ ，q 一 w a ) = 妒，k = j ，j ， 论断9 ( r ) n 正= 妒， 证明：p c # n ( c i + ) n 正，令o ，o 分别是c ，+ 在疋= - - 勺+ ，c i - 】上的第一个邻 点和最后一个邻点，则可o “，白一】p ( h ) i ，否则会得到更长圈 x i c i c c a c j + 一c c j c ，+ ，h x ，令c ，是c ，+ 在五= 可c f + ，c t - 】上的第一个邻点，令是c ，+ 在互= l 【- - c j + ，c ， 上的最后一个邻点，则己【c ，“，c ，- 】旷( 日) l ，否则会得到更长圈 x c 五c ，c j 琶c i c ? c t x t h x ， 现在证明i 已【+ ，c ，一】i + i 己【吒+ ，c f 一】l - l v ( m 1 因为d ( q ，c o ) = 2 ，因为g 是半无爪图，所以存在点“e ( e ) n ( 巳) ，使 n u n c i u n c 】，。n ( c o ) n ( r ( h ) u c ，q ) ) = 庐，( ( c ，) 一 q + ，c i - , c ，q ) = ， 山东师范大学硕士学位论文 贝0 “= e + 或者”= c i 一 若, = c i - ，q - c o e ，则i 己【o ，q 一 卜i 参( h ) i ，否则会得到更长圈 x l c t f c a c j 一瓦+ q c l x i h x , 所以陋r ，c ， l + i 刁t c o + ，c ，一i l - l 矿( - ) 1 若“= c i + ，i ：1 tc b 硭n c , ，得 巳】，则i 己【q + ，q 1 1 + i 己【巳+ ，q 一】i i 矿( ，) l ， 否则会得到更长圈x j c j c j c j + 一c c a c b c c , + a c t x l h x j h - l v ( - ) l + l 己【，】u 己【臼，c 0 1 + 4 己 + ，q 一】l + i 已 巳+ ，c + 陋。”，勺一“可q ”，卅+ c j , c i - , c j + ，c ，c 一，q + ) 4 i y ( 月7 ) l + ( d ( q + ) + 1 ) + 6 ( 4 j 一8 ) + ( 万+ 1 ) + 6 5 d ；一1 ，矛盾 论断1 0 ( r ) n ( e 一 c i 一) ) = 证明：若( r ) ( 、旺一 q 一) ) 妒，令c 。是r 在巧一 c f 一 上的第一个邻点，c a c i + 在五一 c j 一) 上的最后一个邻点，c b 是f 在互= c r ，c j _ 】上的最后一个邻点， 则i _ 【q ”，c ，一 l - l z ( h ) l ，否则会得到更长圈t q 乙，r 两c + c , x , h x , 现在证明i - 【o ，c j _ - 】h 弘+ ，q 一 l - l v ( n ) 1 因为d ( c f ，c b ) = 2 ，因为g 是半无爪图，所以存在点“( q ) n ( ) ，使 n u 】n c , u n c b 】，? n ( c b ) n ( 矿( h ) u ( c ，q ) = 妒，( ，( q ) 一 c f + ，c f 一，c ，q ) = 庐， 则u = c i + 或者”= c i 一 若”= q 一，c i - c b e ，则i 己【o ，c ，一】i + i f c a + , c t - - 1 1 - i v - - i v ( n l ， n - i v ( h ) i + i 己【勺，c 】u 孕【q