（运筹学与控制论专业论文）基本极大（m1）k2free图.pdf

河南大学硕士学位论文 摘要 g 的匹配m 是导出匹配如果 4 1e ( m ) ) = m 。图g 的导出匹配数r e ( c ) ，表 示图g 的一个最大导出匹配的边数。是否存在一个连通不完全简单图g ，对其中每一 对不相邻的顶点z 和玑都有i m ( g + x y ) = i m ( g ) + 1 7 这是一个有趣而且基本的问 题。本文研究了极大2 k 2 一f r e e 图的一些特征，并构造了一些顶点数是1 2 ，1 3 ，1 4 的 极大2 j 岛一f r e e 图。胃是图g 的一个正则导出子图，如果日是图g 的一个导出子图，而 且h g 。我们称g 是一个极大泓+ 1 ) k 2 一f r e e ，如果g 是一个连通非完全简单 图，使得任意给定一对非相邻的顶点z 和y ，i m ( g + x y ) = i m ( g ) + 1 = m + 1 。那 么是否存在三正则极大( 仇+ 1 ) 恐一f r e e 呢? 这个问题仍然是一个o p e np r o b l e m 。 我们说g 是一个基本极大( m + 1 ) k s f r e e ，如果g 是一个极大( m + 1 ) k 2 - f r e e ， 而且图g 的任何一个正则导出子图都不是一个极大+ 1 ) k 2 一f r e e ，其中礼为任意 自然数。设x 是图的集合，我们称一个简单连通图日是x 的一个禁用子图，如果任给 一个图g x ，h 都不是g 的一个导出子图。在本文中我们还将研究上述问题，并 给出的一些禁用子图，其中= g ：g 是一个基本极大( m + 1 ) k 2 - f r e e ，其 中m 为任意自然数，而且g 是三正则图) 。 关键词：导出匹配；导出匹配数；禁用子图；极大2 k 2 - f r e e 图；基本极大( m + 1 1 k 2 一f r e e 图。 河南大学硕士学位论文 a b s t r a c t am a t c h i n gmo fgi si n d u c e d 【4 】i fe ( v ( m ) ) = m t h ei n d u c e dm a t c h i n g n u m b e ro fg ，d e n o t e db yj m ( g ) ，i st h en u m b e ro fe d g e so fam a x i m u mi n d u c e d m a t e l a i n go fg i st h e r ea c o n n e c t e db u tn o tc o m p l e | l ；es i m p l eg r a p hg ，s u c ht h a tf o r e a e l ap a i ro fn o n a d j a c e n tv e r t i c e sza n d 玑i m ( g + z y ) = x m ( a ) + 1 7t h i sp r o b l e m i sf u n d a m e n t a la n dv e r yi n t e r e s t i n g i nt h i sp a p e r ，w ew i l lc o n s i d e rt h ep r o p e r t y o fam a x i m a l2 鲍一如eg r a p t l sa n dc o n s t r u c ts o m em a x i m a l2 兄一f r e eg r a p h so f o r d e r1 2 ，1 3 ，t 4 ，- i sc a l l e d8p r o p e ri n d u c e ds u b g r a p ho fgi f 日i sa ni n d u c e d s u b g r a p ho fgw i t h 日g w ec a l lgam a x i m a l + 1 ) 鲍一f r e eg r a p h ，i fg k s ac o n n e c t e db u tn o tc o m p l e t es i m p l eg r a p h ，s u c ht h a tf o re a c hp a i ro fn o n a d j a c e n t v e r t i c e s 。a n dy ，j 彳( g + z ) = ， 4 ( g ) + 1 = m + 1 1 8t h e r ea n yc u b i cm a x i m a l + 1 ) k j f r e eg r a p h ? t h i sp r o b l e mi ss t mo p e n w es a yg i sab a s i cm a x i m a l ( r n + 1 ) 恐一f r e eg r a p h ，i fg i sam a x i m a l ( m + 1 ) j g f r e eg r a p hw i t h o u ta n yp r o p e r i n d u c e ds u b g r a p ho fgb e i n gam a x i m a l ( 7 , + 1 ) 鲍一f r e eg r a p hf o ra n yn n l e t xb eas e to fg r a p h s ，w es a yas i m p l ec o n n e c t e dg r a p h 日i saf o r b i d d e ns u b g r a p ho f x ，i f ，f o re a c hg r a p hg x ，日i sn o ta ni n d u c e ds u b g r a p ho fg i nt h i sp a p e rw e w i l ls t u d yt h i sp r o b l e ma n di n t r o d u c es o m ef o r b i d d e ns u b g r a p h so f 场= g ：g i sab a s i cm a x i m a l 沏+ 1 ) 一舶eg a a p h ，m 川gi sc u b i c k e yw o r d s ：i n d u c e dm a t c h i n g ，i n d u c e dm a t e h i n gn u m b e r ；f o r b i d d e ns u b - g r a p h ，m a x i m a l2 鲍- - f r e eg r a p h ；b a s i cm a x i m a l ( m + 1 ) 鲍一f r e eg r a p h i i 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位申请。本人郑重声明：所呈交酌学住论又是 本人在导师酌指导下独立完成的，对所研究的课题有新酌见解。据我所知，除 文中特别加咄说明、标注和致谢酌碰方外，论戈中不包括其他人已经发表或撰 写过酌研究成果也不包括其他人为获得任何戢育、科研机构的学位或证书而 使用过酌材料。与我一同工作的同事对本研究所儆的任何贡献均已在论文中作 了明确拍说明并表示了谢毒。 学位串请 、( 孝位论正作者) 釜名 壕莨璃 2 00 1 年6 丹1 日 关于学位论文著作权使用授权书 本人经河南大擘审核 吃准授予硕士学位。作为学位论支的作者本人完全 了解并同毒河南犬擘有关保留、使用学位论正赍勺要求，即河南大学有权向固家 图书馆、科研信息机构、数据收集机构和本棱图书馆等提供学位论文( 虹质五 本和电子卫本) 雌供公欢检索、奎阅。本人撞扳河南大荦出于宣扬、展览学校 学术发展和进行学术交流等目的，可d 采取影印。缩印、扫描和拷贝等复制手 段保存、汇鳊学位论文( 甄质文本和电于支本) 。 ( 涉及保密内客酌学位论文在解密后适用本授权书) 擘住获得者( 学位论工作者) 釜名 挝一一 2 00 1 牟f 月f 日 学位论文指导教师鍪名：盎壹麴 河南大学硕士学位论文 1 引 言 早在上世纪初，图的匹配理论就以不同的方式受到学者的普遍关注，h a l l 1 和 t u f t f 2 1 定理为图的匹配理论的研究奠定了坚实的基础，h a l l 定理给出了一个二部图 有完美匹配的充分必要条件。近百年来，图的匹配理论迅速发展，( l o v a s z 和p l u m m e r ) 【3 1 的专著匹配理论极大促进了图的匹配理论的研究，t u t t e 和l o v a s z 给出了一 般图具有完美匹配的描述，p l u m m e t 提出如下的n 可扩图的概念：设p 和n 为正整数， 且凡0 2 ) 2 。一个p 个顶点的图g 称为扎可扩的，如果图g 的每一个包含n 条 边的匹配都能扩充为一个完美匹配。日d 钯 3 】研究了二部图的n 可扩性。一个图g 成为二l 自界的，如果对图g 的任意一对不相同的顶点u ，口，图g 一让一 有一个完美 匹配。如果一个图是二临界的，则它是1 可扩的。一个有趣的结论是，如果一个图 是2 可扩的，则它或者是二部图或者是二临界的。另外，如果一个图是礼可扩的，则 它也是竹一1 可扩的。 e o 竹记r 饥【4 】给出了导出匹配的定义。我们称一个匹配m 是导出匹配，如果 e v ( v ( m ) ) = m 。对于导出匹配，人们在二部图，3 一正则图和4 一正则图等方面 做出了一系列的结论。 原晋江 5 提出了图的导出匹配可扩性问题对一个简单有限图g ，如果图g 的任意一个导出匹配都包含在一个完美匹配中，则称图g 是导出匹配可扩的。导出 匹配可扩性可以看成是n 可扩性的变异情形。图的1 可扩性在化学图论中有着重要 的应用。注意到导出匹配可扩图一定是1 可扩的，因此导出匹配可扩图的提出可以 看成是1 可扩性的另一个方面的延伸。 八十年代以来，图的匹配理论研究在组合数学，运筹学与控制论中的作用日益 突出，近年来更成为图论及组合最优化中最为活跃的核心课题之一，而图的导出匹 配是近年来兴起的新的研究方向。m e 是g 的一个匹配( l o v d s z 和p l u m m e t ， 1 9 8 5 ) 3 j 如果对每两条不相邻的边e ，m ，满足v ( e ) nv ( f ) = 0 。g 的匹配m 是 完美的( l ( i v a s z 和p l u m m e r ，1 9 8 5 ) 1 3 ，如果v ( m ) = y ( g ) 。g 的一个匹配掰是导出 】 河南大学硕士学位论文 匹配( c a m e r o n ，1 9 8 9 ) 【4 】如果e ( y ( m ) ) = m 。导出匹配的研究在以下著作中都有 介绍( c a m e r o n ，1 9 8 9 ) 【4 ，( f a u d r e ee ta l ，1 9 8 9 ) 【8 】和( h o r a ke ta 1 ，1 9 9 3 ) 【7 】。我 们说g 是导出匹配可扩的( y t m n ，1 9 9 8 ) 【5 】，如果对g 的每一个导出匹配m ，存在g 的 一个完美匹配m + 满足膨m 。为了方便，g 是i m e x t e n d a b l e 表示g 是导出匹配 可扩的。很容易证明每一个i m 。e x t e n d a b l e - - 定有偶数个顶点。一个i m - e x t e n d a b l e 图是极大，如果对每一对不相邻的顶点$ 和口，g + x y 不是一个i m - e x t e n d a b l e 图。 图的i m e x t e n d a b i l i t y 可以看作是n e x t e n d a b i l i t y 的一个变形( p l u m m e r ，1 9 8 0 ) 8 r 一个连通图g 是礼一可扩的，如果i y ( g ) i 2 7 + 2 ，g 有一个完美匹配，并且对g 的 每一个匹配m 满足i m i = n ，存在g 的一个完美匹配m 满足m m + 。本人的导师 宋晓新老师，提出了一个十分有趣的o p e np r o b l e m ：是否存在一个连通不完全简 单图g ，对其中每一对不相邻的顶点z 和y ，都有i m ( g + x y ) = i m ( g ) + 1 7g 是一 个极大( m + 1 1 i 娲一f r e e e 4 ，如果g 是一个连通非完全简单图，使得任意给定一对非 相邻的顶点士和y ，x m ( g + x y ) = i m ( g ) + l = m + 1 1 9 。宋晓新老师在郑州大 学博导原晋江教授组织的有博士与博士后参加的学术讨论班上，作了专门的学术报 告。在武汉会议上，与田丰，赖鸿建，陈冠涛等多位知名学者讨论过这个问题，得到 了广泛地关注，三正则基本极大( m + 1 ) 鲍一f r e e 的存在性问题仍然是o p e n 的， 晓新老师研究了可能存在的三正则基本极大( m + 1 ) k 2 一f r e e 图的一些基本结构性 质，找出了k 的一些禁用子图，并在郑州大学组织的图论研讨会上作了报告。其 中= g ：g 是一个基本极大( m + 1 ) 鲍一f r e e 羽，其中m 为任意自然数，而且g 是三正则图 。本文找出了顶点数为1 2 ，1 3 ，1 4 的基本极大2 凰一f r e e 图，为导出匹配 数和顶点数较小的基本极大( m + 1 ) j g f r e e 图的研究提供了基础。还给出了咒的一 些禁用子图和一些相关的其它结论。 2 河南大学硕士学位论文 2 记号 在本文中，所考虑的图均为有限的非平凡简单图。 给定一个图g ，v v i g ) 和e = e ( g ) 表示它的点集和边集。 对于x y ( g ) ，q y ( g ) ，x 在q 中的邻集 。) = 妇q x ：存在一个点z x 满足叼e ( g ) 。记g v ( x ) = ) 。 对任意的z 矿( g ) ，帕( 妇 ) 简单记作6 ( z ) 。 如果0 = v ，简单记作( z ) 。 x 在0 中的闭邻集记作o ( x ) = xuj ( x ) 。 如果q = v ，简单记作n ( x ) 。 对任意的 v 在q 中的度记作奶( ”) ，q v 。 图g 中的以q 为顶点集的导出子图记作g 旧 。 对于x y ( g ) ，x 中的边集记作占( 习= 锨，e ：让，。x 。 对于x ，y y ( g ) ，从x 发向y 中的边集记作e 僻，y ) ， 从x 发向y 中的边数记作i e ( x 。y ) l 。 对于m e ，记 v ( m ) = 如v ：存在一点。v 满足口z 尬) 。 对于任一个简单图g ，g 的导出匹配数记作 z m ( g ) = m a x ( t i ：m 是g 的一个导出匹配 ， g 的匹配数记作 m ( g ) = m a x ( i m l ：m 是g 的个匹配 ， 记m i m ( g ) = m ：m 是g 的个导出匹配满足m i = ，m ( g ) 。 我们称g 是一个极大( m + 1 ) 鲍一f r e e l 零l ，如果g 是一个连通非完全简单图，使得 任意给定一对非相邻的顶点z 和，i m ( g + z y ) = i m ( g ) + 1 = m + 1 。日是图g 的 一个正则导出子图，如果日是图g 的一个导出子图，而且日g 。我们说g 是一个基 本极大( m + 1 ) 鲍一f r e e 图，如果g 是一个极大( m + 1 ) 恐一f l e e ，而且图g 的任何一 3 河南大学硕士学位论文 个正则导出子图都不是一个极大+ 1 ) 尥一f r e e 虱，其中佗为任意自然数。设x 是图 的集合，我们称一个简单连通图日是x 的一个禁用子图，如果任给一个i 訇g x ，h 都不是g 的一个导出子图。在本文中我们将研究上述问题，并给出j 岛的一些禁用子 图，其中托= g ：g 是一个基本极大+ 1 ) g - , 一f r e e l 虱，其中m 为任意自然数，而 且g 是三正则图) 。 4 河南大学硕士学位论文 3 相关的已知结果 下面是有关图的导出匹配的一些已知结果。 定理3 1 【9 】设g = ( e e ) 是个顶点数为n ，导出匹配数为m 的极大( m + 1 ) j 岛一f r e e 图。那么我们有如下结论： ( a ) 设z ，y ，z kz y e ，y z 隹e 。那么( 。) 一丙( d ，z ) ) 0 。 ( b ) 设u ，u k 删隹e 。那么，m ( g 一( “，口) ) ) = i m ( g ) 。 ( c ) 设= ( g ) 。那么n 一2 i m ( g ) 一4 。 ( d ) 斤( g ) 2 ，其中k ( g ) 表示g 的连通度；如果t = u 1 ，u 2 ) 是g 的点割集， 那么乱l 抛e 。 ( e ) 6 ( g ) 3 并且礼2 1 m ( g ) + 7 。 定理3 2 【9 设g = ( k e ) 是个顶点数为竹，导出匹配数为m 的极大( m + 1 ) k 2 一f r e e 图。t 是g 的一个点割集，凰是g t 的一个分支，那么我们有以下 结论： ( a ) 设和是图g 中不相邻的两个顶点满足丙( 。，) ) t ，那么i m ( h i ) = i m ( h 1 一( 协) ) ) ， ( b ) 设z 和g 是图g 中不相邻的两个顶点满足e ( g 1 一丙( ( z ，订) ) e ( t ) ，其 中g l = g ( 噩) u 邛。令t i = t 一( 协妇) 。那么，m ( 皿一n ( t o ) = 0 。 ( c ) 设t = u l ，毗) 和扎l = i y ( f ) j ，那么n 1 1 0 ，3 ( 皿) 7 7 , 1 4 ，6 ( 日1 ) 2 定理3 3 【9 】设i v i = n ，设g = ( k e ) 是一个顶点数为竹，导出匹配数为m 的 极大( m + 1 ) 鲍一f r e e 图。令= a ( a ) = d ( 1 ) ，i - i l 是g 一( 口1 ) 的一个分支满 足n l = i v ( h 1 ) i 2 ，那么我们有以下结论： ( a ) 对每一个 y ( 风) ，我们有j m ( 玩) = i m ( h 1 一丙( u ) ) 。 ( b ) t , 1 5 ，6 ( 上 ) 2 ；如果佗1 = 5 ，上五是一个5 一圈；如果佗i = 6 ，那 么风= 丑或者乃。如图i 和图2 所示。 5 河南大学硕士学位论文 ( c ) 设g = ( ke ) ，那么礼= i v i 1 2 。 图1图2 定理3 4 【1 0 】设g = ( ke ) 是一个极大( m + 1 ) 9 2 一f r e e 图，满足顶点数l y l = n 和m ( g ) = m ，并且g 是三正则图，那么我们有如下结论： ( a ) g i r t h ( g ) 5 。 ( b ) m ( 3 n 1 2 ) 1 0 。 ( c ) 尤( g ) 3 。 定n 3 5 【1 0 碍。( 1 m 加) 是的禁用子图，其中x c 一 g ：g 是一个极 大( m + 1 ) k 2 - - f r e e 图，m n ，g 是一个三正则图 。( 如图所示) 6 2 ：7 h 5 河南大学硕士学位论文 巩= ( m ，e 1 ) = ( z 1 ，2 ，z 3 ) ， z l 。2 ，x 2 x 3 ，铂$ 1 ) ； 日j = ( k ，e 2 ) = ：( 。l ，$ 2 ，勋，z 4 ) ， z 1 。2 ，。2 $ 3 ，x 3 x 4 ，x 4 x l ) ； 凰= ( v s ，e ) = ( 茹1 ，2 ：2 ，z 3 ，x 4 ，2 ：5 ，u l ，t 也) ， 1 2 2 ，x 2 x 3 ，z 3 x 4 ，x 4 x 5 ，。5 2 1 ，x 2 u l u l u 2 ，抛z 5 ) ) ； 日i = ( k ，e t ) = ( z f ：1 t 1 8 ) ， z z + 1 ：i 1 1 7 o z l z 5 ，x l x 8 ，x 2 x 1 0 ，x 3 x 1 2 ， x 4 x 1 4 ，粕。1 5 ，x 7 2 1 7 ，x g z l 8 ) ) ； = ( ，e 5 ) = ( z t ：1 i 1 7 ) ， 正t 茹件1 ：i 1 1 6 o z l x 5 ，z l x 8 ，x 2 x 1 0 ，x 3 x 1 3 ， x 4 x 1 6 ，x f z l 7 ) ； 日i = ( v o ，e o ) = = 日j x 1 8 = ( k z 1 8 ) ，e 4 z 。z 1 8 ，z l t z l s ) ； 凰= ( v 6 ，屁) = ( v o ，岛u 。l l z l 6 ，) ； 塌= ( v 7 ，e 7 ) = ( v o ，e o u z l l x l t ) ； 凰= ( y s ，e s ) = ( y o ，e o u z 1 3 x 1 7 ) ； 娲= ( 嵋，马) = 凰一x 1 3 ； h l o = ( y l o ，e l o ) = ( y o ，e ou x 9 x 1 3 ) 7 河南大学硕士学位论文 5 4 主要结果 定理4 1 设g = ( ve ) 是一个顶点数为扎，导出匹配数为m 的极大( m + 1 ) k j f r e e 图。那么对每一对不相邻的顶点z l 和z 2 ，都有n c ( z 1 ) b ( z 2 ) 。 证明设g = ( ve ) 是一个项点数为竹，导出匹配数为m 的极大( m + 1 ) 娲一f r e e 图。假设$ l 。2 隹e ( g ) 并且舀( 髫1 ) = n o ( x 2 ) ，对每一对不相邻的顶点茁，z 隹e ，其中z ，y 。2 ，如果能够证明j m ( g z 2 + x y ) = i m ( g z 2 ) + l 成立，就与给定 的条件矛盾。设叼譬e 且，y 。2 ，令m m i m ( g + 茁g ) 。我们分两种情形进行 讨论： 隋形1z 2 隹y ( m ) 。在这种情形下，j m ( g z 2 + x y ) = i m l = i m ( g + x y ) = i m ( g ) + 1 = i m ( g t , 2 ) + l ( 根据定理3 1 ( b ) 我们有i m ( g 一( 。1 ，勋 ) ) = i m ( g x 2 ) = i m ( g ) ) ，矛盾。 情形2 2 y ( m ) 。在这种情况下，设z 2 2 3 e ( m ) ，令m = m z 2 t $ + $ l 3 ， 那么m m i m ( g z 2 + ) ，从而i m ( g z 2 + x y ) = i m ( g + x y ) = i m ( g ) + l = ，m ( g z 2 ) + 1 ，矛盾。这样引理4 1 就被证明了。 定理4 2 设g = e ) 是一个极大2 j 幻一f r e e 图，t 是g 的一个最小点害0 ，那么 我们有如下结论： ( a ) g 一丁有唯一的两个分支日l 和耽，并且岛同构于西。 ( b ) l y ( t ) l 芝3 。 ( c ) 设日1 是g t 的一个非平凡分支，那么对每一个顶点v o v ( 日1 ) ，z m ( 皿一 n ( v o ) 1 = 1 。 ( d ) 设m = i v ( h i ) l ，那么2 ( 风) n 1 3 。如果n 1 = 5 ，那么风是一 个5 一圈；如果n 1 = 6 ，那么h i = 正或乃。如图所示，图1 和图2 。 证明： ( a ) 首先，g t 有唯一的一个非平凡分支，( 否则，- 与i m ( g ) = 1 矛 盾) ，假设皿，凰，日s 是g t 的8 个分支，其c o s 3 ，e ( 皿) o ，其它的分 支凰，日3 ，日。是同构于风。因此，我们有( h 2 ) = ( ) 一= ( k ) = 正其 8 河南大学硕士学位论文 中y ( 皿) = h d ，2 i s ( 注意r 是一个最小点割集) ，与定理4 1 矛盾。( a ) 已经被 证明了。 ( b ) 根据定理3 1 ) ，我们有i v ( t ) i 6 ( g ) 3 。( b ) 已经被证明了。 ( c ) 根据定理3 1 ( a ) ，对每一个v ( h j ，我f f j n i m ( g ) = i m ( g 一丙) = i m ( g 一丙( 伽，如) ) = 1 ，其中k 是王如中唯一的一个点，( c ) 已经被证明了 ( d ) 设卸e ( h 1 ) ，h 2 y ( z 毛) ，则有( 妨一丙( 妇，h 2 ) 0 ，可知，存在 一点m ，满足z m e ( 历) ，同理，存在一点扎，满足y n e ( h 1 ) ，所以6 ( 凰) 22 。 设d ( 。1 ) = a ( h j ，显然有a ( h 1 ) n 1 3 ( 否则，g i m ( g ) = i m ( h ：) = i m ( h 1 一 0 1 ) ) = 1 矛盾) ，所以有2 6 ( 凰) a ( h i ) t l , 1 3 。所以扎1 5 。 如果露1 = 5 ，则( 墨) = 2 ，马是一个5 一圈。 如果m = 6 ，由于j m ( g ) = l 】所以( h 1 ) = 3 ，令d ( v 1 ) = ( 日1 ) ，设矿( 日1 ) = 1 ， 0 2 ， 0 3 ，v 4 ，v 5 ，u 6 ) ，地，u 5 ，n ( v j ，则坳垤e ( 所) ( 否则，i m ( g 一 丙( 勉，口1 ) ) = o ) 。i 打t - i m ( g ) = 1 ，n v a t n ( v j u n ( v 3 ) ，( 。1 ) ( 沈) u ( ) ， 即m ，n ( v z ) un ( v a ) ，显然，佻，不能同时属 - t n ( v 2 ) ( 否呗l j ，i m ( g 一 丙( 也， 1 ) ) = 0 ，x - r 舌) 。不妨设蛳， v 5 ( 2 ) ， 情形l 设”6 ( 。3 ) ，我们得到班= 丑，如图l ； 情形2 设坞， 0 6 ( 协) ，那么砒e ( g ) ( 否则，i m ( g 一丙( ，h 2 ) ) = o ，矛 盾) 。我们得到h i = 乃，如图2 。 下面我们构造一些极大2 j 岛一缸e 囤 根据定理3 3 和定理4 2 ，我们将构造一些2 j g - - f r e e 图。 当g t 的一个分支是5 一圈时，我们构造顶点数为1 2 的极大2 j 幻一f r e e 图g 1 ( 根 据定理3 3 可知i y ( g 1 ) i 1 2 ) 。 定理4 3 对每一个i = 1 ，2 ，设甄= m ，置) 是一个5 一圈，其中k = o i ，h ，q ，也， e j ，毋= 毗饥，魄矗，c f 也，d i e i ，龟吼) 。定义图g 1 ，顶点集为y ( g 1 ) = hu u 危1 ，如) ，边集为e ( g 1 ) = u 冬1 蜀，其中玛= ( 1 ) u 1 。1 ，z 2 ：茁1 k 9 河南大学硕士学位论文 且z 2 ，e 4 = a l a 2 ，0 1 c 2 ，a l d 2 ) u b i b 2 ，b i d 2 ，b l e 2 ) u c 1 0 2 ，c l e 2 ，c l a 2 u f d i d 2 ，如0 2 ，幽6 2 ，u 8 i e 2 ，e z b 2 ，e l c 2 。则g 1 是一个极大2 k j h e e 图。图3 所示。 ( 。2 ，k ，如) 图3 这里o 。( q ，c k ，d 。) 表示町，d 。( n f ) 。 证明：论断1 ：i m ( g 1 ) = l 。 首先我们要证明对每条边。# e ( g 1 ) ，我们有f ( g 1 一( 缸，1 ) ) ) = o 。 如果z = a l b ，那么y ( g 1 一( ，订) ) = k ，d l ，并且f ( g 1 ( p ，讣) ) = 0 。 同理，对每一条边z 晶u 岛，我们有e ( g 1 ( 缸，) ) ) = 0 。如果叫= h l a l ， 那么y ( g 1 一丙( 。，) ) ) = 6 2 ，e 2 ) ，并且e ( g 1 一丙( 伽，) ) ) = 0 。同理可证，对 每条边列e s ，我们有e ( g 1 一丙( 扛，订) ) = 0 。如果鲫= a l a 2 ，那么y ( g 1 一 ( 扣，计) ) = d 。并且e ( g 1 一丙( 扛， ) ) = o 。同理，对每一条边叫e 4 ，我们 有e ( g 1 一丙( 扛，) ) ) = 0 。论断1 被证明了。 论断2 ：对g l 中每一对不相邻的的顶点。a n dy ，我们有i m ( g l + x y ) = 2 。 只需要证明对每一条边铆簪e ( a ，) ，我们有e ( g 1 一( 如，) ) ) d ，那 1 0 河南大学硕士学位论文 么岛就是一个极大2 恐一f r e e 图。设日= 。簪毋：，y k ) ，i = l ，2 设骘= 危1 2 2 ，h 2 x 1 ：z 1 h 并且。2 ) ，设坟= z 1 2 隹e 4 ：z l 并 且z 2 ) 。显然，u 叁1 曰= 列隹e ( g i ) ：$ ，y ( g 1 ) 并且z 衍。 如果z p = 0 1 c l ，那么e ( g 1 一( 茹，) ) ) = h 2 b 2 同样，对每一条边z y 霹u e ，我1 f j 6 e ( g - 一( 和，) ) ) o 。如果z = h 2 a l ，那么e ( g l 一丙( 缸，) ) ) = c t d l ) ，同样，对每一条边z e ，我们有e ( g ，一( 扛，) ) ) o 。如果叫= n 1 6 2 ，那么e ( g l 一( z ，善，) ) ) = c l e 2 ) 。同样，对每一条边铆骘u 曰，我们 有e ( g l 一( z ，9 ) ) ) 0 。论断2 被证明了，因此，g 1 是一个极大2 j 如一f r e e 图a 定 理4 3 被证明了。 下面我们将要介绍一些据有更多的点的极大( m + 1 ) j 已一f r e e 图，当g 一丁的一 个分支是丑，我们构造一个图g 2 。 h 1 讹( 忱口2 ”3 ) 图4 在这里蛳( 吩讥u 。) 表示叼，l k ，( 毗) 。 定理4 4 设皿= ( k ，置) 是一个5 一圈，其中k = 铆，他，钍3 ，铂，) ，e 1 = 社1 撕，u 2 u a ，撕m ，“4 讹，u 1 。设f f 2 = ( ，易) ，其中= u 1 ，也，7 1 3 ，v 4 ，地，v 6 1 1 河南大学硕士学位论文 ，易= 1 地，口1 5 ，饥v 6 ，也m ，忱坞，t j 2 姐，v 3 v 6 。我们定义图g 2 ，顶点集为y ( g 2 ) = k uk u h 1 ，也 ，e ( c 2 ) = o l l 目，边集为易= h l h 2 u 1 茹1 ，h 2 2 2 ：x l 并 且。2 ) 和e 4 = “l m ，“1 也，“1 ) uu 2 v l ，w 2 v 3 ，u 2 m ，u 2 v s u u 3 u 2 ，世3 v 4 ，抛佻， u 3 ) uu 4 v l ，u 4 v 2 ，u 4 u 3 ) uu s v 3 ，坞恤，“5 ，u 5 口6 。那 么g 2 是一个极大2 乜一f r e e 图。如图4 所示。 证明：论断1 ：i m ( c 2 ) = 1 。 只需要证明对每一条边删e ( g 2 ) ，我们有e ( g 2 一( 和，订) ) = 0 。如果z = v l v 4 ，那么y ( ( 如一丙( 。，) ) ) = 。3 ，h l ，并且e ( g 2 一( ( 。，) ) ) = 0 。同理 可证，对每一条边列易，我们有e ( g 2 一( 忙，订) ) = 口。如果列= u l w 2 ， 男v z , v ( a 2 一( 扛，疗) ) = ，“4 ) ，并且e ( g 2 一( z ，疗) ) = 0 。同理可 证，对每一条边叼e 1 ，我们有e ( g 2 一( z ，订) ) = 0 。如果叫= k 口1 ，那 么v ( a 。一( z ，) ) ) = 让3 ，“5 ) ，并且e ( g 2 一丙( 扣，疗) ) = 0 。同理可证，对 每一条边铆岛，我们有e ( g 2 一( 扛，) ) ) = o 。如果z = u l 地，那么矿( g 2 一 丙( 。，) ) ) = u 3 ，) ，得到e ( g 2 一丙( 扛，订) ) = 0 。同理可证，对每一条 边z 甄，我们有e ( g 2 一( z ，口 ) ) = o 。论断1 被证明了。 论断2 ：对g 2 中每一对不相邻的的顶点。和y ，我们有i m ( g 2 + x y ) = 2 。 只需要证明对每一条边z 隹e ( g 2 ) ，我们有e ( 岛一丙( z ，订) ) 0 ，这里 的g 2 是一个极大2 鲍一f r e e 图。设骘= z f 隹且：口，y k ，其中t = 1 ，2 。 设珑= h 现， 2 。1 ：z i m 并且。2 k ) 和耽= p 1 。2 隹& ：x l 并 且z 2 ) 。很显然，u 叁1 露= ( z 隹e ( g 2 ) ：茹，y y ( g 2 ) 并且z 订。 如果= u l u 3 ，那么e ( g 2 一丙( z ，) ) ) = 协) 。同理可证，对每一条边z 可 e ；u e ；，我们有e ( g 2 一丙( 扛，们) ) o 。如果鲫= h i u l ，那么f ( 岛一( 扛，) ) ) = v 2 v 3 ) 。n n , - i 证_ ，对每一条边列忍，我们有e ( g 2 一( 以 ) ) 口。如 果z = u 1 “3 ，那么e ( 岛一( z ，g ) ) ) = u 3 u 5 ) 。同理可证，对每一条i , 盘z y 坟， 我们有e ( g 2 一丙( 。，) ) ) 0 。论断2 被证明了。 1 2 河南大学硕士学位论文 因此，g 2 是一个极大2 k 2 一f r e e 图。定n 4 ，4 被证明了。 当g t 的一个分支是乃，我们构造一个图g 3 ， 定理4 5 设h 1 = ( k ，e 1 ) ，其中- - - u l ，坳，饥，乱4 ， 1 , 5 ，) ，e 1 = u l v a ，u l u 5 ，u l 锄， u u 2 u 5 ，u 2 u 3 u u 3 u 8 ，“3 4 ) u 4 u 6 ) u u 5 蛳) 设z 易= ( k ，岛) ，定义k = 口1 ，砚，v 3 ，v 4 ，v 5 ，) ，j 乞= v l v 4 ，u 1 ，v l v 6 u v 2 v 3 ，v 2 v 4 ，v 2 v s w ( v 3 v 5 ，v 3 v 6 u v 4 v d 。设g 3 是这样一个图，顶点集为y ( g 3 ) = v i u v 2 u h l ，k ) ，边集e ( g 3 ) = u 乞1 毋，其中e 3 = h l k ) u h l x , ，如茁2 ：x l 且现) 并 且且= “1 v 2 ，u 1 0 4 ，u l 0 5 ，i t l v 6 u u 2 v l ，地也，忱姐，u 2 v 6 o u 3 v 3 ，乱。讹，3 t 嵋，u 3 v e u 蛳”1 ，u 4 v 2 ，地如，u 4 v 4 ，) u u s v l ，奶姐，u s v 4 ，坞坞) u 珧 1 ，u e v 2 ，u e v 5 ，) 。那 么g 3 是一个极大2 一f r e e 图。如图5 所示，。 h 1 0 3 0 4 ) 图5 这里啦( q 口k u 。) 表示， o k ，u 。，沁) 。 证明，论断1 ：i m ( g z ) = 1 。 只需要证明对任一条边z 口e ( g 3 ) ，我们有e ( g 3 丙( 0 ，g ) ) ) = o 如 河南大学硕士学位论文 果删= 札- u 2 ，那么矿( g 3 一( 如，订) ) = 粕， ，得到e ( g 3 一( 扛，y ) ) ) = 0 。同 理可证，对每一条边x y e l u 场，我们有e ( g 3 一( 。，) ) ) = 0 。如果。= h 2 v l ， 那么矿( g 3 一丙( 忙，) ) ) = 让z ，蛳) ，我们有e ( g 一( p ，计) ) = o 。同理 , - 7 i 正，对每一条边锄e 3 ，我们有f ( g 3 一丙( p ，) ) ) = o 。如果z = l 2 v 1 ，那 a v ( g z 一丙( z ，可) ) ) = 口。此时，e ( g 3 一丙( 如，订) ) = 0 。同理可证，对每一条 i 2 z y e 4 ，我们有e ( g 3 一丙( $ ，订) ) = 口。论断1 被证明了。 论断2 ：对任两个不相邻的顶点z 和g ，z 和属于g 2 ，我们证明j m ( g 3 + $ ) = 2 。 只需要证明对任意一条i , 2 l x y ，x y 岳e ( g 3 ) ，我们有e ( g 3 一丙( q ，f ) ) ) 日， 此时g 3 是一个极大2 j 如一f r e e 图。设曰= ( x y 叠忍：z ，y k ，其中t = 1 ，2 。设露= 愚l z 2 ，：g l ：。i m 和z 2 k ) 。令坟= f z l z 2 隹e 4 ：x l h 且。2 k 。很显然，l 瞧1 曰= 鲫叠e ( g 2 ) ：z ，y v ( a 2 ) 且z 订。 如果g = u l “3 ，那么e ( g 3 一丙( ，订) ) = 九2 ”1 ) 。同理可证，对每一条边列 日u 忍，我们有e ( g 3 一( k 订) ) 0 。如果聊= h l v l ，那么e ( 岛一( 扣，办) ) = ( 也u 3 ) 。同理可证，对每一条边叼懿，我们有e ( g 3 一丙( z ，口) ) ) 0 。如 果。= a 1 u 1 ，那么e ( g 3 一( 扛，订) ) = t 啦吨 。同理可证，对每一条边铆坟，我 们有e ( g 3 一丙( z ，f ) ) d 。论断2 被证明了。 因此，g 3 是一个极大2 k 2 一f r e e 图。定理4 5 被证明了。 定理4 6 。( 1 1 m 1 3 ) 是x c 的禁用子图，其中澎= g ：g 是一个极 大( m + 1 ) 凰- f r e e 图，m n ，g 是一个三正则图) ， 巩1 = ( h 1 ，e n ) = ( z 1 ，工2 ，x 3 ，x 4 ，z 5 ，z 6 ，2 7 ，z 8 ， ， 2 1 x 2 ，。2 2 3 ，x 3 x 4 ，x 4 2 5 ，x s x 6 ，z 6 2 1 ，z l 7 ，茹7 8 ，2 8 2 4 ) ； 且j 2 = ( k 2 ，e 1 2 ) = ( z ：l i 1 0 ) ， $ l o t + 1 ：i 1 9 u x l x l o ，x 1 0 2 5 ，观施，x 9 2 4 ) ； 历3 = ( m 3 ，e 1 3 ) = ( 筑：1 i 8 ) ， 。 岛+ 1 ： 厶，u x l x 6 ，x l z 8 ，x 4 x 8 ，x 7 2 3 ) ； 1 4 河南大学硕士学位论文 图凰2图日1 3图凰1 证明：假设趣l 不是x c 的禁用子图。设g 1 1 x c 满足皿1 是g 1 1 的一个导出子 图，设舰1 m i m ( g 1 l + x 3 x 6 ) 。如果；t 8 隹y ( 尬1 ) ，那么 矗1 一x 3 x 6 + x 3 x 4 是g l l 的一个导出匹配，矛盾。所以z 8 y ( f 1 1 ) 。同理，z 7 以1 。 我们有断石8 y ( 尬。) 。设蕊，= 尬l z 3 钆，x 7 玩 ，那么( y ( 厩，) ) 妄 v ( g n )