（应用数学专业论文）p3控制图和（k142）图的圈和路.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得 ( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名：宋麦埯娟 导师签字： 学位论文版权使用授权书 鼻 芝淬 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：幂女局女局 导师签字： t 1 )匆 参俨 签字日期：2 0 0 孑年4 月? ；日签字日期：2 0 0 矽年v 月码日 山东师范大学硕七学位论文 心一控制图和( ，。4 = 2 1 一图的圈和路 宋娟娟 ( 山东师范大学数学科学学院济南。山东2 5 0 0 1 4 ) 中文摘要 圈和路是图的两种基本结构是分析和刻画图的有力工具大量的实际问题 都可以归结为图的圈和路问题对图的圈路性质的研究是在图论中的著名问题 一爿r ，r ，“f ，c i 问题的基础上发展来的而关于图的哈密顿性的研究已经取得了 长足的发展这方面的研究成果和进展可参见文献f 2 铒 2 9 1 图的圈路性质一直 是图论中的热门研究领域经过几十年的发展圈路性质所涉及的内容日益丰富 和具体圈的方面包括图的日。仇m d ”圈最长圈j ( 点) 泛圈完全圈可扩点不交 的圈圈覆盖等等：路的方面包括图的日o m 淝鲫路( 可迹性) 最长路h 口m m d 连通泛连通路可扩等等另外在图连通性方面一些学者不断提出新的概念 比如人2 一局部连通三角连通匹角连通等为图的圈路性质的研究提供了新的 思路 由于直接研究一般图的圈路性质往往比较困难所以若干年来相关的研究 主要集中在一些特殊匿类上即不含有某些禁用子图的匡类其中比较有代表性 的是无爪图它是以凡1 3 为禁用子图的图类继b c i l l c k l 9 g 6 1 9 7 0 年发表的关于 线图性质的两篇文章i 3 0 j j 3 l i 之后人们就开始关注包这种含着线图的无爪图 7 0 年代末8 0 年代初是研究无爪图的个非常活跃的时期至今在这方面已取 得了相当多的研究成果另外无爪图的概念也被从不同角度推广到了更大的图 类如爪心独立图半无爪图几乎无爪图( k 。口：g ) 一图拟无爪图等近年来一 些新型图类不断被提出r 一控制图就是其中一种这种图类包含半无爪图是半 无爪图的推广2 0 0 6 年南开大学的两位访问学者h j b r o e r s m a 和e 、，u m a r 首 次提出了b 一控制图的概念。并得出一系列成果。参见文献( 2 1 本文主要对只一 控制图进行了初步探索得出其圈路方面的几个结果另外还讨论了( k - a ：2 ) 一 图的点泛圈性 在第一章中我们主要介绍了本文的研究背景和已有的一些结果以及文章 中所涉及的一些概念和术语符号 在第二章中我们具体讨论了2 一连通r 一控制图在两个条件下的日o m 沈觎 性得到下面的结果： 1 山东师范大学硕士学位论文 2 定理2 6 设g 是2 一连通的b 一控制图且g 中不含同构于人，2 3 的导出 子图如果g 的每个同构于z l 的导出子图都具有性质圣z ，( 6 1j 或圣z ，( n 厶2 ) ： 则g 是h n r r “d 7 ，的( 其中么l 如图2 1 中的图) 定理2 7 设g 是2 一连通的p 3 一控制图且g 中不含同构于a ，2 3 的导出 子图如果g 中每个同构于乙的导出子图都具有性质圣z 。( 乜1 6 1 ) 和西z 。( 0 1 6 2 ) 则g 是日n m i f o 饥的( 其中幺如图2 2 中的图) 在第三章中：研究了( k 1 4 ：2 ) 一图的点泛圈性得到下面的结果： 定理3 1设图g 是6 ( g ) 4 的连通( k 1 4 ：2 ) 一图如果g 中爪心独立且 g 的每个同构于z 1 的导出子图都具有性质垂而( n 6 1 ) 或中而( n f 2 ) 那么g 是点 泛圈的( 其中z 1 如图2 1 中的图) 在第四章中研究了2 一连通b 一控制图的最长圈证明了下面的结果： 定理4 5 设g 为竹阶2 一连通岛一控制图如果g 中不含同构于尬3 的 导出子图则g 中最长圈的长至少为m i n n ：2 6 + 4 ) 在第五章中研究了p 3 一控制图的赉次可迹性证明了下面的结果： 定理5 1 1设g 是2 一连通的p 3 一控制图t 7 ( g ) p 是g 中一条最长 的 一路若ly ( 尸) 17 ( g ) 1 那么对v 肌f e ( 17 ( g p ) 、厂( p ) 一p ) ) ( 其中 z 、( g p ) u ( 1 ( 尸) 一 t ) ) ) ：有u u + e ( g ) 定理5 2 3 若g 为，阶3 一连通r 一控制图满足( ，学则g 是并 次可迹的 定理5 3 2 若g 为 阶2 一连通p 3 一控制图满足c 学则g 是芹 次可迹的 关键词：b 一控制图：( 人r 1 4 ：2 ) 一图：点泛圈性：哈密顿性： 次可迹性 分类号：0 1 5 7 5 o nc y c l e sa n dp a t h so f 忍一d o m i n a t e dg r a p h sa n d ( k 1 4 ：2 ) 一g r a p h s j u a n j u a ns o n g s c h o 。lo fm a t h e m a t i c a ls c i e n c e s 。s h a n d o n gn 。r m 越u n i v e r s i t y j i n a n ? s h a i l d o n g 2 5 0 0 1 4 p r c h i n a a b s t r a c t ly c l e sa n dp a t h s 盯( 、t mh a s i ( 。s t r u 订1 1 r e so fg r a p l l s m c a n w h i l e t h ( 、v a r ( ，a l s o e t 抬c t l t o o 上st oa n a l y z e 铲a p h m a n 、p r a c t i c a lp r o b l e m sc a nb pa t t r i b u t e d t ot h e p r o b l c n lo c y c l e sa i l dp a t l l s t h es t u d ) 7o i p r ( ) p e r t i e so f ( y c l ea n d p a t hc o n l e sf r o n l t n en a m l j t o np r o b l e m 职血i c l li st h ef 赴o u st o p i ( i ng r a p h t h e o r 、t h er e s e a r c ho f n a m l l t o n l c l t 、h a sm a d ea 铲e a tp r o g r e s s t h er e s u l t sa n da d 、r a n c e si nt h j s a s p e c t c 鲫b er 硝e r e dt o 【2 6 j 2 9 j t h es t u 曲o ng r 印h s c y c l ea n dp a t hi s a l w 郴a na c t l v e 士i e i dm g r a p ht h e o r 、a t e rt h ed e v e l o p m e n tf o rd o z e n so fw a r s t h ec o n t e n t s l np r o p e m e 80 士g r 印h s 唧1 ( 、a n dp a t hb o m ( 、m o ma n ( 1 m o r cr i c ha 1 1 ds t ) e ( | i 能 上n ep r o p e r t l e so c y c l ei n c i u d eh a m i l t o nc y c l e 1 0 l l g e s t c y c l e ( 、7 e r t e x 。) p a n c v c l i c i t v v e r t e x d 1 s 1 0 1 m c y c l o c o i i l p l c t e b c ) c l t c x t c n d s j b i l i t ) a i l ds oo n ：t l i cp r o p e r t i e so f p a t h1 1 1 c j u d eh a m i l t 。np a t h ( t r a ( e a b i l 竹j 1 0 n g e s tp a t h p a n ( o n n e c t i 、t i r 、lt ) a t he x t e n d s l 叫1 t ) 。a n ds ( jo n i o r eo 、e ：i nt h ip a r io fg r a p h s c o n n e c t j 、r j r j ，s o m es c h o l a r s d e n n e dm a n ) n e wc 。n c e p t sc o n t i n u o u s l ，s u c ha l s 一l o c a l l ) c o n n e c t t r i a n g u i a 爪 c o r u l e c q u a d r a n g u l a 坶c o n l l e c ta n ds oo n w h i c hp r o 、r i d e sn e wt h i l l k i n g sf o rt h e s t u d ) o fp r o p e r t i e so fc 、c l ea n dp a t h 1 1 8u s u a l 卜、c h d i f f i ( u ht us tu 小i j r o p c r t j 燃o fc y c ka l l d p a t l ii nt 1 i o s ( 1g i a d l l s w l t h 。u fa 町r e s t r i c t i o n s ot l l e - o r ki nt h i sa s p e c t i sm a i n l ) a i m e da ts p e c i n lg r a p h c l a s s e 5w n l c ha r et h eg r 印h sn o tc o n t a i n i n gs o m ef o r b i d d e n s u b g r a p h s t h eo n em o r e r e p r e s e n t a t l v pc j a s si sc 1 勰。矗供g r a p l l m i c hi st h eg r 印hw i t hn oi n d u c e d ，】3 t h e n r s tm o t l v a t l o n o rs t u 蛳n gp r o p e r t i e so fc l a w f r e e 弘a p h s 印p a r e n t l ) a p p e a r e d 矗o m b e m e k e8c h a r a r o e r i z a t j o no f l i n pg r a p h s i n 3 0 j f 3 1 h o w e v e r t h em a i ni m p l l l s pt h a t t u r n e dt n ea t t e n t l o no ft ng r 印h t h e o r 、c o m m u n i t 、t ot h ec l a s so fc l a w f r e eg r a p h s w a s9 1 v c l lml a t e7 0 sa n dc a r l ) 8 0 s t h e r e1 l 硒b o e nal o to f r c s u l t so nc l a 弘f r e e g r 印hu pt on o w i na d d i t i o n t h ed e f i n i t i o no fc l a w f r e eg r a p hh a l s b e e ne x t e n d e d os e v e r a ll a r g e rg r a p hf a m i l i e si nd i 雎r e n tv i e w s ? s u c ha l s c l a w c 朗t e r i n d e p e n d e n t 3 山东师范大学硕十学位论文 4 g r a p h q u a s i c l a 矾- f t e ( 、g r a p h s a l m o s tc l a w f r e ( 、g r a p h s ( 凡l ，：g ) 一g r a p h s s t r o n 9 1 ) a l m o s tc l a w f r e eg r 印h se t c i nr e c e n tv e a r s s o m en e wg r 印hc l a s s e sh a v eb e e nd e - f i i l e dc o l l t i i m o u s l ) o i l eo fw l l i c hi s 亿一d o l l l i i l a t e dg r a p h i n2 0 0 g h j b r o c r s i l l aa i l d e v u m a rg a v et h ec o n c e p t i o no ft h ep 3 一d o i l l i n a t e dg r a p h w h e nt h e ) v i s i t e dn a n l ( a i u n i v e r s i t ) a n dt h e ) ha _ v eo b t a i n e das e r i e so fr e s u l t sw h i c hc a nb er e f e r e dt o 2 ： i nt h i sp a p e r 弋7 l 陀m a d eap r e l i m i n a r ) s t u d ) o np 3 一d o m i n a t e dg r a p h sa n do b t a i n e d af e r e s u l t s i na d d i t i o n 译s t u d i e dt h ev e r t e x - p a n c y c l i c i t yo f ( k 1 4 ：2 ) 一g r a p h s i nt h e 矗r s tc h 印t e r w eg i v eab r i e fi n t r o d u c t i o na b o u tt h eb a s i ( c o n c e p t s t c r i l l i i l o l o g i e sa 1 1 ds ) 7 n l b o l sw h i c h 7 i l lb cu s e di nt h i sp a p e r i i lt h em e a n t i h l c ，、 r e a l s og i v es o m er e l a 上e dr e s e a r c hb a c k g r o u n d sa n ds o m ek n o w nr e s u l t s i nt h es e c o n dc h a p t e r mm a i n l s t u d ) h a m i l t o n i c i t ) o fb d o m i n a t e dg r a p h s u n d e rt v oc o n d i t i o n sa n dg i v et h ef 0 1 l o w i n gr e s u l t s ： t h e o r e m 2 6l e tgi sa2 一c o n n e c t e d 尸3 一d o m i n a t e dg r a p hw i t hn oi n d u c e d k 2 3s u c ht h a te v e r yi n d u c e dz lo fgs a t i s 矗e s 圣z l ( n ：6 1 ) o r 圣z l ( o 6 2 ) t h e ngi s n ，n i h d n i n n ( z 1i sa si nf i 9 2 1 ) t h e o r e m 2 7l e tgi sa2 一c o n n e c t c dr d o m i n a t e dg t a p l lw i t hn ( ) i n d u c c d 虬3s u c ht h a te v e r ) i n d u c e dz 毫o fgs a t i s f i e s 圣z ? f n l 6 1 ) a n d 圣z ? ( a 1 6 2 ) t h e ng i s n ，礼i 2 d n i n 礼( z ji sa si nf i 9 2 2 ) i nt h et h i r dd l a p t e r w em a i n l ) s t u d ) 、，e r t e x p a n c y c l i c i t = ) o f ( 人14 ：2 1 一g r a p h s a ，i l ( 1 ( ) 1 ) t a i i i “le 、r e s u l ta s “) 1 1 ( 娜1 7 s ： t h e o r e m3 1l e tgi sac o n n e c t e d1 人，l ，4 ：2 ) 一g r a p hw i t hm i n i m u md e g r e ea 1 e a s tf 6 u ra n di n d e p e n d e n tc l a w - c e n t e r ss u c ht h a te v e r yi n d u c e dz 1o fgs a t i s 丘e s 西z l ( c 【6 1 ) o r 西z 1 ( n 6 2 ) t h e ng i su e 7 z e 。一p n n c y c 2 沈( z 1i sa si nf i 9 2 1 ) i nt h ef o u r t hc h a p t e r ，em a i n l ) s t u d j l a r g e s tc y c l e so f2 一c o n n e c t e d 尸3 一 d o m i n a t e dg r a p h sa n dg i v et h ef 6 i i o w i n gr e s u l t ： t h e o r e m4 5l e tgi sa2 一c o n n e c t e db d o m i n a t e dg r 印ho n 礼v e r t i c e sw i t h n oi n d u c e dk 2 ，3 t h e i ll e n 酵ho ft h c1 a r g e s tc y c l e so fgi sa t1 e a s tm i ”2 6 + 4 i nt h el a s tc h 印t e r w eg i v et h ef o l l o w i n gr e s u l t sa b o u tb d o m i n a t e dg r 印h s ： t h e o r e m5 1 1l e tgi sa2 一c o n n e c t e dp 3 一d o 工n i n a t e d 擎a p h ：秽y ( g ) ， a n dpi st h el o n g e s tp a t hw i t h 1 7 ( 尸) l iv ( g ) i ，s u c ht l l a t i fv z 豇e ( y ( g p ) y ( p ) 一 u ) ( z y ( g p ) 乱( y ( p ) 一 r ) ) ) ，t h e nu u + e ( g ) 山尔师范，：学硕士学位论文 t h e o r e m5 2 3l e tgi sa3 一( o n n e r t p d 尸3 一d o m i i l a f e dg r a p ho nnv e r t i r o s i fn f 呈学t h e ngi sh o m o g e n e o u s l ) t r a c e a b l e t h e o r e m5 3 2l e tgi sa2 一c o n n e c t e d 尼一d o m i n a t e dg r a p ho n 门v e r t i c e s i f f 垒宇：t h e ng i sh o m o g e n e o u s l ) 。t r a c e a b l e k e y w o r d s ：r d o i l l i n a t e dg r a p h ：( 凡1 4 ：2 ) 一g r a p h ：v e r t e x p a n c ) r c l i c 啦：h a m i l t o n i c i t v ：h o n l o2 ：e i l e o u s l 、t r a ( c a b l i n c l a s s i f i c a t i o n ：0 1 5 7 5 5 山东师范大学硕士学位论文 6 一、研究背景 第一章预备知识 1 1 研究背景及已有结果 图的h a m i l t o n 性是图论研究中的热点问题之一一百多年前爱尔兰数学家 哈密尔顿提出了这样个问题：一个连通图有h a m i l t o n 圈的充分必要条件是什 么? 这就是著名的哈密顿问题该问题一经提出就受到广泛关注后经研究发现 它是个n p c 问题， 对图的圈路性质的研究是以哈密顿问题为起点发展起来的相关的研究主 要集中在两个方面：一是寻找图具有某些圈路性质的充分条件，二是研究某些特 殊图类的圈路性质后者中的特殊图类主要是指不含某些特定结构的导出子图 的图类这些特定结构的导出子图又称作禁用子图无爪图就是以k 1 3 为禁用 子图的图类由于其深刻的研究背景一一线图都是无爪图上个世纪的七八十年 代无爪图受到图论界的广泛关注对无爪图的圈路性质的研究也是在这个时期 开始的 经过几十年的发展图的圈路性质所涉及的内容日益丰富和具体比较常 见的圈的方面有哈密顿圈( 点) 泛圈性完全圈可扩性等：路的方面有可迹性 h a m i l t o n 连通泛连通性路可扩性等同时从无爪图的禁用子图 ，- 3 的结构出 发又相继定义了一些新的图类如几乎无爪图半无爪图( k - p ：q ) 一图等等一 方面人们尝试把无爪图中的结论推广到更大的图类另一方面人们也希望得到 这些新的图类在圈路方面的一些新的结果 基于以上研究背景本文选择了p 3 一控制图和( k l ，4 ；2 ) 一图中的圈路性质作 为研究的内容主要沿着推广已有结论和探索新结果两个思路进行研究 二、已有结果 山东师范 ：学硕士学位论文 1 9 9 8 年李明楚在 3 j 中给出了下面的两个结果： 定理2 1 设g 是2 一连通无爪图且j f g ) 23 如果g 中同构于z l 的导 出子图都具有性质西z 。f 9 6 1 ) 或面z 。( n 6 2 ) 那么g 是点泛圈的( 其中图z l 如图 2 1 中的图) 定理2 21 3 设g 是2 一连通无爪图且( i ( g ) 3 如果g 中同构于邑的导 出子图都具有性质圣旋( “1 1 ，1 ) 和m z ：( r f l f 七) 那么g 是点泛圈的( 其中图五如 图2 2 中的图) 同年，a a i l l o u c l l c 在 4 中定义了半无爪图并探讨了它的“仃，j ，t d 性得到 如下结果： 定理2 3 ( 4 】设g 是2 一连通半无爪图且g 不含同构于邑的导出子图则 g 或者是一个圈或者是泛圈的( 其中图历如图2 2 中的图) 2 0 0 6 年啦晓英在 5 中将李明楚的结论推广到了半无爪图得到如下两个 结果： 定理2 4 【5 设g 是顶点数不小于3 的连通半无爪图如果g 中同构于z 1 的导出子图有性质垂而6 1 ) 或圣z ，6 ：) 那么若g 有r ) 一匿则g 必有 ( 。? 。1j 一匿：其中4 r | 1 ( g jf ( f 1 ( g j z 1 如图2 1 中的图j 定理2 5 5 j 设g 是顶点数不小于3 的连通半无爪图：如果g 中同构于邑 的导出子图有性质圣历( c 1 1 6 1 ) 和圣勿( q 1 6 2 ) 那么若g 有( n rj 一圈则g 必有 ( o r + 1 ) 一圈( 其中4sr i17 ( g ) f n 1 ( g ) 汤如图2 2 中的图) 1 9 8 5 年m m a t t h e m s 和d s u m n e r 在 1 1 ：中证明了以下结论： 定理4 1 f 1 1 】n 阶2 一连通无爪图有长至少为m i 扎 n 2 6 + 4 ) 的最长圈 2 0 0 0 年李明楚将其推广到几乎无爪图： 定理4 2 【1 2 】n 阶2 一连通几乎无爪图有长至少为玎“n ( n ，2 ( f + 4 ) 的最长圈 7 山东师范j ：学硕士学位论文 8 2 0 0 5 年蔺厚元在 1 3 】中研究了( 人- 1 4 ：2 ) 一图和半无爪图得出结论 定理4 3 阶2 一连通( k 1 4 ：2 ) 一图6 3 时有长至少为m i n n 2 6 + 4 】 的最长圈 定理4 4 门阶2 一连通半无爪图最长圈的长至少为m 砌 几2 6 4 ) 1 9 9 1 年r f a u d r e e r j g o u l d t l i n d q u e s t e r 在 1 9 给出结论 定理5 2 1 【1 9 j 若g 是饥阶3 一连通无爪图满足c2 学则g 是次 可迹的 2 0 0 6 年王玉丽在 2 0 中将其推广到半无爪图：得到结论 定理5 2 2 【2 0 若g 是n 阶3 一连通半无爪图：满足c 学则g 是： 次可迹的 定理5 3 1 f 2 0 若g 是竹阶2 一连通半无爪图：满足c 学则g 是。 次可迹的 1 2符号概念介绍 本文仅考虑有限无向简单图所使用的记号和术语约定如下其中未加说 明的部分请参照文献1 i 设g 是一个图：i 厂( g ) e ( g ) 分别表示g 的顶点集和边集对于口z ，可 y ( g ) ，s 丁v ( g ) 及g 的子图日令 ( u ) = 札y ( g ) ：u 口e ( g ) ) ，m = ( t ，) u r ) ： r s ( u ) = ( u ) ns 帆( 丁) = u 。丁k ( u ) ， s ( h ) = 帆( y ( ) ) ，( 丁) = 蜥( 日) ( 丁) ， e ( s ，丁) = s e ( g ) ：s s ! 丁 ， 山东师范大学硕十学位论文 f = m i n 引( z ) ua ( 箩) l ：z 矽、f g ) z 夥f g j ) g 的由s 导出的子图记为 。f l = 旷( ) ：称为的阶 将图g 中与掣关联的边的数目叫做顶点t 的度记为d g ( 1 ，) 即始( u ) = l n ( 1 在不至引起混淆的前提下也简记为f ，) 用巧。f ? 分别表示g 中顶点的 最小发和最大度也常简记为j 对于扎2 1 f ) 若( 训na ( z ) 1 f ) o ： 则称g 的子图日满足性质西胃( 仳z t ) 如果图g 中不存在七一1 个顶点的集合分离g 则称g 是序一连通的图g 的连通度k ( g ) = m a x ( 七：g 是七一连通的 设t ，l ，- ( g ) 如果( t ) 的导出子图 是七一连通的则称t 是g 的一个局部七一连通点如果图g 的每一 个顶点都是局部鼯一连通点则称g 是局部菇一连通的 设p = z l z 2 - 勋为图g 的一条路。巧17 ( p ) ( 1 i j ) 用z _ 2 和z - 。分别表示p 上的点蜀一! 和z + f ：z 产1 和_ 1 也分别记为z - z _ ：用。 尸奶 和z j 瓦f ( i j ) 分别表示p 的子路z ，函+ 1 乃和z 广l z 记z 尸z 力= o z ，。1 一 17 ( j o 再，) = 一1 - 一z 。) 设f = t 17 ，2 t 1 是图g 中的匿? ot ，、( f ) f 1si j ，) 用t _ 7 和 y 产7 分别表示f 上的点一f 和q + f i f 1 和1 产1 也分别记为y 厂和t 产：用f ! t o 和 t 万码分别表示f 上的路t ? f 2 _ + 1 t o 和。i 仇一1 i 这里点的下标均模r ) 以g 的顶点t 为一端点的路叫做g 的t 路以g 的顶点仉t t 为两端点的 路叫做g 的( u t ) 一路设尸是g 的一条( u 2 - ) 一路如果g 中不存在( u u ) 一 路尸使得v ( p ) cv ( p ) 且l 尸7 l j 尸f 则称p 为g 的一条极短( u ：t ，) 一路显 然连通图中任意两点之间都有极短路以顶点u f 为两端点的最短路的路长叫 做仳t ，之间的距离记为d ( 乱r ) 经过g 中每个顶点恰好一次的路( 圈) 称为( g 的) 日d m m 觎路( 圈) 以t ，为 一个端点的n m 砒。九路称为( g 的) u 一日口m 砒d n 路若g 中存在一个日o m 妣o n 9 山东师范大学硕士学位论文 圈则称g 是哈密顿的若g 中存在一条日口m m d n 路则称g 是可迹的如果 对咖g g 中都有? ，一“m 矶c ， 路则称g 是并次可迹的 如果对v “t v ( g ) 图g 都有f u 钞) 一h a m i l t o n 路则称g 是日n m m d 竹连 通的若v 仉t 1 ( g ) 图g 都有长为f ( f f ( ，l ? ，) 7 ( g ) l 一1 ) 的m 1 ，) 一路 则称g 是泛连通的如果图g 满足：对v 札：t t g ) 及g 的任意一条( u ：2 t ) 一 路p 只要( 尸) j 、7 ( g ) i ：就存在g 的( t t ，) 一路p 7 使得1 7 ( 尸) c 、7 ( 尸) 且 ( 尸引= ( 尸) 1 + 1 则称g 是路可扩的满足条件的p 7 叫做尸的扩路 令( g ) f = 几若对任意的整数f ( 3 f 礼) g 中都有长为白勺圈则称图 g 是泛圈的：对v t 一y ( g ) 及满足3 f 竹的任意整数f 若g 中存在包含点 t t 的长为f 的圈则称图g 是点泛圈的：并记包含点u 的长为f 的圈为( 口f ) 一 圈如果图g 满足：( 1 ) g 的每个顶点都在长度为3 的圈上：( 2 ) 对g 中任 意一个圈c 只要l 7 ( f ) i i v ( g ) | 就存在g 的圈c 7 ，使得v 7 ( f ) cv ( f 7 ) 且 ( f ，) l = 1 1 r ( c ) i + 1 则称g 是完全圈可扩的 设p 3 是一整数，g 中同构于k l ，的子图叫做g 的一个p 一爪用 表示以 z o z l ：卸) 为顶点的一个p 一爪：并约定记号中的 第一个顶点表示该p 一爪中的p 度顶点：称为爪心若对g 的任意一个p 一爪 均有ie ( ) l q 则称g 为( k 1 p ：g ) 一图易证 ( k l ，p ：q ) 一图一定是( 凡l ，p + 1 ；q + 1 ) 一图( k 1 3 ；1 ) 一图即为无爪图故( k 1 4 ：2 ) 一图 包含无爪图是无爪图的推广若g 中任意两个3 一爪的爪一已、均不相邻则称g 是爪心独立的并记g 的爪心独立集为d ( g ) 对v z v ( g j 令，( z ：) = u a r ( z ) n ( 耖) i 【u r u m ) ，j 7 ( z ，y ) = u ( z ) n ( 剪) l 对 v t ( 札) z y ) ：满足z 口，妒隹e ( g ) 且【( z ) u ( y ) u ( u ) z ：3 ，u ) ( ) ) 若d ( z ：y ) = 2 时：j ( z y ) d 则称g 是半无爪图：，7 ( z ，剪) uj ( z ! 可) 0 则称g 是 尸3 一控制图显然：无爪图一定是半无爪图，半无爪图一定是b 一控制图反之 不然，例如鲍3 是p 3 一控制图，但不是半无爪图 1 0 山东师范大学硕士学位论文 第二章2 一连通b 一控制图的日o m 淝m 性 2 0 0 6 年，h j b r o e r 8 m a 和e l i n a r 两位学者在南开大学访学期间首次提出 了b 一控制图的概念，并得出一系列成果本章讨论了b 一控制图在两种条件 下的日口m m m 性 定理2 6 设g 是2 一连通的b 一控制图，且g 中不含同构于鲍3 的导出 子图，如果g 的每个同构于五的导出子图都具有性质圣而( 口，6 1 ) 或圣z ，( 口，6 2 ) ， 则g 是日n m 砒伽的( 其中历如图2 1 中的图) 定理2 7 设g 是2 一连通的b 一控制图，且g 中不含同构于鲍3 的导出 子图，如果g 中每个同构于汤的导出子图都具有性质圣历( 口l ，6 1 ) 和圣z 2 ( 口l ，6 2 ) ， 则g 是h 彻m t o n 的( 其中历如图2 2 中的图) 下图2 1 和2 2 分别表示历和z 2 图2 1图2 2 在证明这两个定理前，先来看一个有用的引理： 引理2 8 ：【2 】设g 是2 一连通的b 一控制图，且g 中不含同构于3 的导 出子图，令c 是g 的最长圈若iy ( c ) l iy ( g ) i ，则对讹( g c ) ，有 u 一乱+ e ( g ) 山东师范大学硕士学位论文 证明：令日是g c 的一个连通分支，t = a ( 日) ，因为g 是2 一连通 的，所以ltl 2 任取黜e ( y ( 日) ，y ( c ) ) ( z y ( 日) ，t y ( c ) ) ，显然 舢；一，z u + 簪e ( g ) ( 否则有更长圈) 假设u u + 盛e ( g ) ，根据，的定义显然有 t 正隹j ( z ，t 一) u 厂( z ，缸+ ) 下证t ，( z ，u 一) n ，( z ，让+ ) ： 因为d ( z ，钍一) = 2 ，所以j ( z ，t 一) u ( z ，t 一) d 假设j 伽牡使得伽 厂( z ，u 一) u ，( z ，t 一) 如果 车y ( c ) ，显然可得更长圈z 缸c t 一z ，所以叫y ( c ) 如果j ( z ，t 一) ，则伽一) mu 阻一】，显然z 伽一隹e ( g ) ，所 以t l j t i 一e ( g ) ，可得更长圈z 让c 叫一t 一乙z ，此矛盾说明伽( z ，t 一) ，而 伽一) ，t ) ，由，的定义知叫一u e ( g ) ，再根据的定义分两种情 况讨论： 当t t ，+ t 一时，t t 7 一硼+ e ( g ) ，则z t 正c 伽一叫+ c 钆一伽z 是一更长圈，矛盾 2 7 当 + = t i 一时，考虑d ( u 一，u + ) = 2 ，贝0 | 名j ( t 一，让+ ) u ( u 一，u + ) ，显然 名y ( c ) ，否则易得更长圈z u 钍一z t + c z ( 1 )若z j ( 仳一，t + ) ，显然名仳，t t j ，叫一，否则易得更长圈矿( z ) 阻一】u 心+ 】：当矿t 一e ( g ) 时，z 札c 名让一矿c t j z 是一更长圈；当z + u + e ( g ) 1 2 时，z 扎仳一2 乙+ 名+ c 伽z 是一更长圈，矛盾 若名，( u 一，矿) ，显然名u ，伽，伽一，否则易得更长圈当名让+ 2 时，名一矿e ( g ) ，z u 伽一虿z + z 一乙+ 名钍一伽z 是一更长圈；当z = t + 2 时，考虑d ( z ，矿) = 2 ，则j 伽7 ，( z ，乱+ ) u ，( z ，矿) ，类似于伽只须讨论训7 ，( z ，矿) 且伽7 = 让+ 2 时的情形，此时伽7 = 名，z z = z 叫7 e ( g ) ，由于矿( 名) 且z ( 乱一，u + ) ，所以 z + z e ( g ) ，得更长圈名z 矿c 2 ，矛盾 以上证明说明叫= u ，所以必有乱j ( 茁，u 一) u ，( z ，u 一) ，而札簪，( z ，u 一) ，所 以仳( 。，u 一) 同理可证缸，( z ，乱+ ) 应用上面结论可推出日= 【z 】- ，否则由j 7 的定义，让+ ( u ) 与z 在日中的 所有邻点相邻，从而易得更长圈因为g 是2 一连通的，所以珈( 日) u ) ， 即伽e ( g ) 因为u ( z ，u 一) ，所以由j 7 ( z ，乱一) 的定义可知札+ e ( g ) ，同 山东师范歹：学硕士学位论文 理可知u 一2 f g ) 显然，“一z 1 。或u 一t 否则 竺凡2 3 ? 一 圣e ( g ) 否则有更长圈州j ( ，t 一t 一r ? 厂t m 这样由于f 7 ( z t + j = 2 类似于 易证t j 7 ( z t + ) n ，7 ( z t 一) 因为t ，一芒 ? ( t + ) n ( z ) 并且“一a ( u ) 从而 t ，一材一e ( g ) 可得更长圈? ? ，f u t 一孕u z 推出矛盾引理证毕 定理2 6 的证明： 设图g 是满足定理2 6 的条件下证g 有o m m o 圈 用反证法设c 日丁z u 的取法与引理2 8 中相同由引理2 8 知豇一u 一e ( g ) 则 兰z 1 所以满足性质西z ，( z “+ ) 或圣z ，( z “一) 由对称性不妨 设满足性质中z ，f z t f + ) 即j a i f z ) n ( u 1 。) 且剪“u 一：若可g c ) 显然有 更长匿：t 广( j 7 ：若r f 17 ( f ) f ，+ 2 和t 厂2 否则有更长圈：( ? t 厂u + 枷和 z y 虿u + u u z 由弓i 理2 8 可知可一y + e ( g ) 贝0 有更长圈z y “+ c y 一可+ c 札z 矛盾 定理2 6 证毕 定理2 7 的证明：设g 满足定理2 7 的条件下证g 有日“m m d 九囤用 反证法取g 中一最长匿c 3 ! l ( c ) f j g ) 令r = g c 医为g 是 2 一连通的