（运筹学与控制论专业论文）关于图的因子与分数因子的若干结果.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名- i ! 煎导师签名：论文作者签名：i ：竺封导师签名：叛期：q 晷 关于图的因子与分数因子的若干结果 关于图的因子与分数因子的若干结果 卞 秋 菊 ( 山东大学数学与系统科学学院，济南2 5 0 1 0 0 ) ( 指导教师：刘桂真教授) 中文摘要 二十世纪六十年代以来，图论已经成为发展最快的数学分支之一应用图论来 解决运筹学、化学、生物学、网络理论、信息论、控制论、博弈论和计算机科学等 学科问题已显示出极大的优越性图论在各个学科分支、工程技术领域及社会科学 有着广泛的应用，它作为组合数学中的一个分支，受到了各方面的普遍重视 因子理论是图论的一个重要分支，在图论研究中得到了极大关注在日常生活 中，许多诸如编码设计、积木设计，计算机网络的文件传输、进度表等关于运筹和 网络设计问题都涉及到图的因子，因子分解和正交因子【2 】其中，文件传输问题可 以模拟为因子和( 0 ，) 一因子分解( 或，一染色) ，拉丁方块和空间方块的设计则涉及 到图的因子和正交因子问题 本文所考虑的图都是有限简单图设g 是一个图，v ( g ) 是顶点集，s ( c ) 是 边集对v ( g ) 的子集s ，g s 表示由y ( g ) s 导出的子图，g 旧表示由s 导出 的子图图g 的点割是v ( g ) 的子集s ，使得g s 是不连通的k 点割是有k 个 元素的点割g 的连通度一( g ) 是使得g 有k 一点割的最小的k 图g 称为是k 一连 通的若仡( g ) 2k 图g 的边割是e ( g ) 的子集【s ，v ( c ) s 】，其中s 是v ( g ) 的非 空子集七边割是有k 个元素的边割g 的边连通度a ( g ) 是使得g 有一边割 的最小的k g 称为k - 边连通的若a ( g ) k 令g 和，是两个整值函数且对所有x v ( c ) ，0 墨9 ( x ) s ，( z ) 图g 的( g ，) 一 因子f 是g 的支撑子图且对所有x v ( c ) ，满足g ( z ) d f ( x ) ，( z ) 若对任 意。v ( g ) ，9 ( z ) = y ( x ) 。则( 9 ，) 一因子称为，一因子对非负整数k 和所有 z v ( g ) ，若，( o ) = 尼，则，一因子称为k 一因子特别的，若对任意z v ( g ) ， g ( z ) = ，( 。) = 1 ，( 9 ，) 一因子称为1 一因子，即完美对集。图g 的完美对集可参见 2 2 卜 s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 分数( g ，) 一示性函数h 是一个函数分配给图g 的每一条边一个 0 ，1 】之间的数 使得对每一个点z v ( c ) 有g ( 。) d c 。( 茁) ，( 。) 其中d c x ) = 。b ( e ) 是点 z v ( e ) 的分数度，且忍= e ：e = x y e ( g ) ) 令h 是图g 的分数( g ，) 一示性函 数令e h = e ：e e ( g ) 且 ( e ) o ) 若g h 是g 的支撑子图使得e ( e ) = e h ， 则g h 称为g 的( g ，) 一因子当对任意x v ( g ) ，g ( z ) = o 且f ( z ) = 1 ，则这个 分数示性函数是分数对集的示性函数若g ( x ) = f ( x ) = k ，则分数( g ，) 一因子称为 分数k 一因子当对任意o v ( c ) ，g ( x ) = ，( 2 ) = 1 ，则分数示性函数是分数完美 对集的示性函数，即分数1 一因子 对图的因子的研究始于一百多年以前1 8 5 9 年，r e i s s 证明了鲍。可被分解 成1 一园子1 8 9 1 年，j p e t e r s o n 证明了任意偶数度图可以分解成边不交2 一因子 的并他还指出2 一连通3 一正则图有1 一因子这两个结果可被认为是现代因子理 论的先驱为了将对集理论从二分图推广到一般图( 即非二分图) ，1 9 4 7 年t u t t e 9 5 给出图有l 一因子的判定准则这个完美的理论或许是因子理论中最基础的结果 1 9 5 2 年q ：l 1 t t e 9 6 】又给出了图有，一因子的判定准则l o v i s z 7 3 l 得到了图有( g ，) 因子的充分必要条件从此，关于因子的大量结果不断涌现出来 分数图论是相对年轻的分支关于这方面的第一本专著是由c l a u d eb e r g e l l 9 】 在1 9 7 8 年写的分数图论1 9 9 7 年e r s c h e i n e r m a n 和d h u l l m a n 写了一本新 的分数图论教材，其中包括分数匹配、分数边着色、分数着色和分数同构等几乎所 有允数图论所涉及的内容在图论中遇到的整数值常量几乎都可以给出它的类似的 分数形式 本文分为六章，主要讨论了五个方面的同题( 1 ) 二分图中的( 9 ，) 一因子；( 2 ) 甄1 n - 自由图中的因子；( 3 ) 一般图中的( g ，) 一园子和分数( g ，) 一因子；( 4 ) 关于图 的分数可扩性的推广；( 5 ) m 因子临界图 第一章我们给出了简短的但较完整关于图的因子和分数因子的综述 第二章分两部分来研究二分图中的( g ，) 一因子一部分是讨论与连通度，边连 通度有关的( m g ，m ，) 一二分图存在特殊( g ，) 一因子的充分条件，并指出这些结果在 某种意义下是最好的另一部分给出了二分图中的一个新的韧度并研究了该韧度和 ( 9 ，) 因子存在性的关系 定理2 1 4 设g = ( x ，r e ( g ) ) 是( m g ，m f ) 一二分图，且g 和，定义在v ( g ) u 关于图的因子与分数因子的若干结果 上的正整值函数满足对所有茁y ( g ) ，9 ( z ) ，( z ) ，其中k = 。? 犯) 9 ( z ) 令d 是e ( g ) 的子集且i d i = m + r ，r 0 若( a ) f ( x ) = ，( y ) ，g ( x ) = 9 ( y ) ，( b ) m k k ( g ) c ( g 【d ) + r + k ，且( c ) 对所有z y ( g ) ，i d n e ( z ) i ( m 一1 ) ，其 中e ( x ) 是g 中与点。关联的边，则g 有一个( g ，) 一因子不包含d 定理2 1 5 设g = ，y e ( g ) ) 是( m g ，m 1 ) 一二分图且其边连通度a t e ) 满 足m 七x ( g ) 2n 且m 2 ，其中g 和，是v ( g ) 上的正整数函数使得对所有 茁y ( g ) ，有k g ( z ) f ( x ) ，i ( x ) = i ( r ) 且g ( x ) = 9 ( y ) 则g 有一个( 9 ，) - 因子不包含任意i n + r l j 条边 在定理2 1 4 中对所有z v ( v ) ，令，( z ) = 9 ( z ) 我们有如下结论 推论2 1 6 1 7 0 1 设g 是m ，二分图，令d 是且i d i = m + r ，r 0 若( 。) 托( g ) c ( g 【d ) + r + k 其中对所有x v ( v ) ，k = m i n f ( x ) ：z y ( g ) ) 且( b ) d g d ( z ) 芝 ，( o ) ，则g 有一个，一因子不包含d 在定理2 1 。4 和定理2 1 。5 中对所有z y ( g ) 分别令，( z ) = g ( z ) = l _ 则有如 下结论 推论2 1 7 1 5 0 1 设g 是正则m - ：9 - 图令d 是边集e ( c ) 的子集且i d i = m + r ， r 0 若k ( g ) 4 a i d ) + r + 七，5 ( g d ) 1 ，则g d 有一个完美对集 推论2 1 8 设g = ( x ，e ( g ) ) 是正则m _ 二分图，边连通度入( g ) 礼且 m 2 则g 有一个完美对集不包含任给的l 下n + li 条边 c h v d t a l 【2 9 l 第一次介绍了韧度的概念，记作 l q l t ( g ) = m i n i 尚：s y ( g ) ，u ( g s ) 2 ) ， 其中u ( g s ) 表示g s 中的分支数且g 是非完全图若g 是完全图，则t ( g ) = o o 随后许多学者研究了韧度与哈密尔顿圈或因子的关系刘桂真，马英红7 5 1 定义了 图的另一个参数一孤立韧度 邶) = r a i n 捣：s 刚g ) ( a - s ) 2 ) 其中i ( g s ) 记为g s 的孤立顶点数且g 是非完全图若g 是完全图，则 ，( g ) = o 。显然( g ) ( g ) 钱建波在【8 6 】中给出- f - - 分图中与韧度有关的参数 以g ) = r a i n 捣：s c _ x 或y , 郴删 2 ) ， 1 1 1 s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 其中g 是非完全二分图否则芒，( g ) = 0 0 他研究了t 7 ( g ) 与【a 6 卜因子或，一因子 的关系 我们在二分图中定义了一个新的孤立韧度 ，7 ( g ) = m i n f 。i ( g 坠- ) l s ) ：s 冬x 或 ( g s ) 2 ) 其中g 是非完全二分图否则，( g ) = 。o 显然，( g ) 三t 7 ( g ) 我们用这个参数来 刻画二分图的( g ，) 一因子 定理2 2 3 设g = ( x ，e ( g ) ) 是二分图且g ，f 是v ( c ) 上的正整数函数 使得对z v ( a ) ，a g ( x ) ，( z ) 茎b ，其中o ，b 是整数且2 a b 令 x i = i y i = n2 ( a + b - 1 ) ( 。a + b - 2 ) - i ，d ( g ) 兰b 且，) = ，( y ) ，g ) = 9 ( y ) 若 ，( g ) ! 导，则g 有一个( 9 ，) - 因子 定理2 2 4 设g = ( x ，e ( g ) ) 是二分图且g , f 是v ( c ) 上的正整数函数使 得对所有o v ( g ) ，a g ( x ) f ( x ) b ，其中a ，b 是整数且l 茎asb 令 i x i = l y l = n ，f ( x ) = f ( y ) 且g ( x ) ；9 ( y ) 若7 ( g ) 习赢n i - 1 二j ，则g 有一个 ( g ，) 一因子 在第三章中我们集中考虑凰，自由图中的因子，其中n 3 k 1 矿自由图有 很多好的性质在这里我们得到了k 1 旷自由图有( 9 ，) 一因子或是( ，；m ) 一均匀图 的与最小度有关的充分条件 s u m n e r 9 2 得到了任意连通的偶阶无爪图有完美对集e g a w a 3 1 】给出了k l n 自由图有七因子的度条件何乐亮【4 1 】得到了k 1 ，。一自由图包含f 一因子的度条件 我们推广了【3 1 ，【4 1 j 和【9 2 l 中的结果，在一般意义上得到了耳l ，。一自由图有( g ，) - 因子的充分条件 定理3 1 1 设a ，b 是非负整数，g 是连通的k n 一自由图，9 ，f 是v ( c ) 上 的整数函数且对所有z v ( g ) ，若9 ( x ) = ，( z ) 有。v r g l ，( 。) 是偶的如果 2 几一1 a so ( z ) ，0 ) sb 且 职) ；+ 学+ 志+ 掣+ 簪+ 莩， 则g 有( g ，) 因子 在定理3 1 1 中令g ( x ) = ，( z ) ，即可得到 4 1 中结果 w 关于图的因子与分数因子的若干结果 推论3 1 2 1 4 1 】设o ，b 是非负整数，g 是连通的k 1 旷自由图9 ，是v ( a ) 上 的整数函数且对所有x v ( c ) ，2 n 一1 a 墨f ( x ) sb ，。y f ( x ) 是偶的 若 邪，2 ；+ 掣+ 志+ 掣+ 等+ 竽， 则g 有，一因子 在推论3 1 2 中令d = b = ， 3 1 】中结果成立 推论3 1 3 【3 1 1 设2 是非负整数，g 是连通的k 1 旷自由图且k l v ( a ) i 是偶 的若6 ( g ) 2 莉n 2 k + ! 暴+ 掣则g 有k 一因子 我们还考虑了k t 矿自由图是( ，；m ) 一均匀图的度条件这个结果改进并推广了 【6 l 】和【6 5 中的结论 定理3 2 4 设a ，b ，n 和m 是非负整数且b a 礼+ 2 m = n 令g 是( m + 1 ) 一 边连通图且对所有z v ( c ) ，f ( x ) 是v ( g ) 上的整数函数且满足a 墨f ( x ) 墨b 和 。州g ) f ( x ) 是偶的若g 不包含k i ，。作为导出子图且 即，；+ 端+ 稿+ 躺+ 舄+ 掣， 则g 是( ，；m ) 一均匀图 推论3 2 5 令a ，b ，礼和7 7 是非负整数且b n n + 2 设g 是2 一边连通图且对 所有z v ( a ) ，( z ) 是v ( a ) 上的整数函数且满足a f ( x ) b ，：y ( g 】f ( x ) 是偶的若g 不包含k 1 。作为导出子图且 邸峨b + 端+ 蒜+ 躺+ 嵩+ 竿， 则g 是，均匀图 第四章从不同角度研究了一般图中的( 9 ，) 一因子和分数( g ，) 一因子例如邻 域并，连接数和导出子图等等得到了图有( g ，) 一因子或分数( g ，) 一因子的与这些 参数有关的充分条件并且这些结果在某种意义下是最好可能的 近年来，越来越多学者考虑邻域并条件和因子的关系并出现了很多结果 n i s s e n 8 1 】研究了邻域并和k 一因子存在的关系m a t a s u d a 7 8 1 研究了邻域并和 【口，6 】一因子我们证明了如下有关( g ，) 一因子存在性的结论，这是f 7 8 ，8 1 中结果的 推广 v s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 定理4 1 3 设。和b 是非负整数，g 是n 阶图且礼 她趔攀，6 = 6 ( g ) i ! 生2 垒2 a g ，f 是y ( g ) 上的整数函数且满足o g ( ) 坦# 9 和，是v ( g ) 上的整数函数且满足1 曼n 9 ( 茁) 蜓a n 逊- ( 堕a + = 垒b ) 丑+ 3 或 6 ( g ) 甭b a - i ，则g 有分数( g ，) 一因子 本章的最后我们考虑图g 的( g ，) 一因子和其连通的导出子图，得到了如下结 果 定理4 3 4 设g 是连通图，且p 是整数满足0 p v ( g ) i 令，是v ( g ) 上 的整数函数且对所有。v ( g ) 满足2s ( x ) d c ( 。) 假设g 的每一个p 阶的连 通导出子图日有分数( g ，) 一因子，则g 有分数( g ，) 因子 第五章我们分三节考虑分数对集可扩性首先我们定义图的分数亏格一d 对集， 给出了图有分数亏格d 对集的充要条件且研究了分数亏格一d 对集与韧度的关系 其次，我们定义了( n ，知，d ) 图并讨论了它的性质，这些性质是分数情形特有的最 后，我们研究了硒旷自由图中的分数可扩性 c b e r g e 1 8 j 定义了亏格一d 对集，即g 中有一对集恰好覆盖了g 中l y ( g ) j d 个顶点他同时给出了亏格d 对集存在的充要条件。我们定义图的分数亏格d 对 集设g ，是g 的分数对集，若它的每一个分支或者是边或者是奇圈或者是孤立点 且满足龉( t j ) = ，( e ) = 0 的孤立点个数恰是d ，则g ，是g 的分数亏格一d 对集 显然分数亏格- 0 对集就是分数完美对集 v 1 关于图的因子与分数因子的若干结果 定理5 1 9 设g 是一个图，d 是非负整数且0 d i y ( g ) l 一2 ，g 有分数亏 格一d 对集当且仅当 t ( g s ) si s l + d 对任意s y ( g ) 而且若g 是二分图i y ( g ) i ；d ( m o d 2 ) 定理5 1 1 0 设g 是一个图，d 是非负整数且0 sd l v ( g ) 卜2 若t ( c ) 半， 则g 有分数亏格一d 对集 设g 是一个图，礼，七，d 是非负整数且n + 3 自+ d 墨i v ( g ) l 一2 假定g 有k 条 边的对集对g 中任意k 条边的对集m ，若存在一个分数完美对集g 包含m 且 对e e ( m ) ， ( e ) = 1 ，则g 被称为分数k - 可扩的我们也称m 可扩充为g 的 分数完美对集若去掉g 中任意竹个顶点剩余子图g 有一个k 一对集且任一女一对 集可扩充为分数亏格。d 对集，则g 是分数( n ，d ) 一图下面我们总假设扎，k ，d 满 足礼+ 3 七+ d l v ( c ) i 一2 我们先给出( n ，k ，d ) - 图的一个性质 定理5 2 1 图g 是分数( n ，后，d ) 一图当且仅当下列条件成立 ( i ) 对任意s v ( g ) 且l s l n ，则t ( g s ) 1 s l n + d ( i i ) 对任意s y ( g ) ，i s l 礼十2 k 且c s 包含一个k 一对集，则i ( g s ) s i s l n 一2 k + d 定理5 2 4 分数( 几，k ，d ) - 图g 也是( n 7 ，k 7 ，d ) 一图，其中0 n 7 竹，0 7 k 我们还研究了对( n ，k ，d ) 一图去掉一条边的影响 定理5 2 7 若g 是分数( n ，k ，d ) 一图，则对任意e e ( g ) ，g e 是分数( n 一 1 ，k ，d + 1 ) - 图 对分数( n ，d ) 一图在礼= 0 时下面结论成立，而佗0 时此结论不成立 定理5 2 8 图g 是分数( k ，d ) - 图当且仅当对任意i 条边的对集m ，图g v ( m ) 是分数( k i ，d ) 一图 第五章的第三节讨论了k l m 自由图是分数k 一可扩的与连通度有关的充分条 件 定理5 3 2 设g 是奇阶( 2 + 2 ) 一连通的k 1 ，k + 3 一自由图且爪心是独立的则g 是分数k 一可扩的 当l y ( g ) f 是偶的，定理5 3 2 的连通度是( 2 七+ 1 ) 推论5 3 3 设g 是奇阶2 - 连通的无爪图则g 有分数完美对集 v l l s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 推论5 , 3 4 设g 是奇阶( 2 + 2 ) - 连通的无爪图，则g 是分数七可扩的 第六章主要讨论扎因子l 临界图和分数扎- 因子l 临界图首先，我们讨论分数 m 因子临界图的性质 在【8 1 】中给出了图的最大对集和伽因子临界图的的关系，我们考虑了图的最 大对集和分数礼_ 因子临界图的关系 定理6 1 4 设g 是连通图且m 是g 的任意( 特定) 的最大对集若对任意 e m ，g y ( e ) 是分数m 因子临界的则g 是分数m 因子临界的 其次我们研究了分数因子临界图和它的完全闭包 定理6 2 。2 设g 是p 阶图令v ( a ) = 嚣1 ，) 则g 是分数m 因子临界 图当且仅当对1 is 睦+ 礼) ，g 乞是分数m 因子临界图，其中g ：。是由g 在甄 局部完全化得到的 定理6 2 3 设g 是+ 七) 连通图令o v ( a ) 且口( g 【g ( z ) 】) 尼其中 角2 令g 是由g 在z 局部完全化得到的若g 是分数( n 十女一1 ) 一因子临界 的，则g 是分数扎- 因子临界的 定理6 2 4 令s 和七是整数且8 3 ，后2 设g 是( n 4 - ( s 1 ) 七一1 ) 一连通图 且g 中导出图k 1 。的中心是独立的，令z 是g 中一点满足7 ( g n c ( x ) 】k 且令 g 7 是由g 在。局部完全化得到的若g 是分数4 - ( s 一2 ) k 一1 ) 因子临界的， 则g 是分数扎因子临界的 图g 称为( o ，k n ) 一l 晦界图若去掉g 的扎个顶点，剩下的图仍有【n ，6 】一因子 滕聪f 9 7 】给出了图g 的韧度的最好的界保证了g 是( 2 ，6 ；礼) 一临界图我们还研究 了图g 的韧度和( o ，6 ；礼) 一临界图且推广了【97 和【1 0 5 中的结果 定理6 3 4 令g 是一个图， 2so 丽i n 再- 1 再，t h e ng h a so ( g ，f ) - f a c t o r i nc h a p t e r3w ep a yo u ra t t e n t i o nt ot h ef a c t o r si nk 1 t n - f r e eg r a p h s ，w h e r en23 k 1 - n - f r e eg r a p h sa r ek n o w nt oh a v em a n yi n t e r e s t i n gp r o p e r t i e s ，h e r es o m es u m c i e n t c o n d i t i o n sr e l a t e dt om i n i m u md e g r e ea r eo b t a i n e df o rak 1 ，n f r e eg r a p ht oh a v ea ( g ，) 一f a c t o ra n dt ob ea n ( ，；m ) - u n i f o r mg r a p h ，r e s p e c t i v e l y s u m n e r 9 2 】o b t a i n e dt h a te v e r y e v e nc o n n e c t e dc l a w - f r e eg r a p hh a sap e r f e c t m a t c h i n g e g a w a 3 1 】g a v et h em i n i m u md e g r e ec o n d i t i o n sf o rk 1p n - f r e eg r a p h st o h a v eak - f a c t o r h e 4 1 o b t a i n e das u f f i c i e n tc o n d i t i o nr e l a t e dt om i n i m u md e g r e ef o r k 1 f r e eg r a p ht oc o n t a i na n ，一f a c t o r w eg e n e r a l i z et h er e s u l t si n 【3 1 ， 4 1 】a n d 【9 2 t h u si nt h eg e n e r a lc a s ew eg e tt h es u f f i c i e n tc o n d i t i o nf o rk 1 i n - f r e eg r a p ht oh a v ea ( g ，) 一f a c t o r t h e o r e m3 1 1l e ta ，bb en o n n e g a t i v ei n t e g e r sa n dgb eac o n n e c t e dk 1 。n 咖e g r a p h 9 ( 。) ，f ( x ) i s 饶en o n n e g a t i v ef u n c t i o n sd e f i n e do nv ( g ) s u c ht h a t2sn 一1 a g ( x ) ，( 。) 6 m o r e o v e ri f g ( z ) = f ( x ) f o ra l lx y ( g ) ，。州g ) f ( x ) i se v e n i | 即b + 学+ 志+ 掣+ 百n - 1 + t 2 n - 5 ， t h e ngh a sa 【g 。1 ) - f a c t o r s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n l e tg ( x ) = ，( 。) i nt h e o r e m3 1 1 ，w eg e tt h er e s u l t si n 4 1 】 c o r o l l a r y3 1 2 1 4 1 1l e tn ，bb en o n n e g a t i v ei n t e g e r sa n dgb eoc o n n e c t e dk 1 n f r e eg r a p h f ( z ) i st h en o n - n e g a t i v ef u n c t i o n sd e f i n e do nv ( g ) s u c ht h a t2 n 一1 os ，( z ) 掣学a n d5 = 6 ( g ) 警，l e tg ，fb et w op o s i t i v e i n t e g e r - v a l u e df u n c t i o n sd e f i n e do nv e r t e xs e tv ( c ) o fgs u c ht h a tas9 ( z ) 掣l e tg ，fb et w op o s i t i v ei n t e g e r - v a l u e df u n c t i o n sd e f i n e d o nv e r t e xs e tv ( c ) o f gs u c ht h a t1 凸曼g ( z ) 鱼a 二n - 必( a 巴+ 幽b ) + 3 o r e ( c ) 丽b n - i ，t h e ng h a snf r a c t i o n a l ( g ，) 一f a c t o r i nt h el a s to ft h i sc h a p t e rw ec o n s i d e rt h ef r a c t i o n a l ( g ，) - f a c t o r sa n dc o n n e c t e d i n d u c e ds u b g r a p h s w eo b t a i nt h ef o u o w i n gr e s u l t t h e o r e m4 3 4l e tgb eac o n n e c t e dg r a p h , a n dpb ea ni n t e g e rs u c ht h a t0 p i v ( a ) 1 l e t ，b ei n t e g e r - v a l u e d 知n c t i o nd e f i n e do nv ( g ) s u c ht h a t25f ( x ) 茎d c ( x ) x v s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n ，0 ra l lo y ( g ) s u p p o s et h a te v e r yc o n n e c t e di n d u c e ds u b g r a p hho fo r d e rpo fg h a s 口f r a c t i o n a l ( g ，) - f a c t o r t h e ngh a s 口f r a c t i o n a l ( 9 ，) - f a c t o r i nc h a p t e r5 ，w ef o c u 唧o nf r a c t i o n a lm a t c h i n ge x t e n s i o na n dd i v i d e di ti n t ot h r e e s e c t i o n s f i r s tw ed e f i n et h ef r a c t i o n a ld e f e c t dm a t c h i n go fag r a p h t 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 r8g r a p ht oh a v eaf r a c t i o n a ld e f e c t dm a t c h h t ga r eg i v e na n d t h er e l a t i o nb e t w e e nt h ef r a c t i o n a ld e f e c t dm a t c h i n ga n dt h et o u g h n e s 8i sd i s c u s s e d s e c o n d l y , o nt h eb a s e so ff r a c t i o n a ld e f e c t dm a t c h i n g ，w ed e f i n et h ef r a c t i o n a l ( 礼，d ) 一 g r a p ha n dd i s c u s si t sp r o p e r t i e sa n dt h e s ep r o p e r t i e sa r es p e c i a lf o rf r a c t i o n a lf a c t o r f i n a l l y , w es t u d yt h ef r a c t i o n a lm a t c h i n ge x t e n s i o ni nk i ，n f r e eg r a p h c b e r g e 1 8 1d e f i n e dd e f e c t dm a t c h i n gw h i c h am a t c h i n go fgc o v e r se x a c t l y l y ( g ) l dv e r t i c e so fg an e c e s s a r ya n ds u f i i e n tc o n d i t i o nf o rag r a p ht oh a v e ad e f e c t - dm a t c h i n gw a sg i v e nb yh i m w ed e f i n et h ef r a c t i o n a ld e f e c t dm a t c h i n g s u p p o s et h a tg ii s 8f r a c t i o n a lm a t c h i 】唱o fg ，i fi t se v e r yc o m p o n e n ti sa ne d g e o ra no d dc y c l eo r8 ni s o l a c e dv e r t e xa n dt h en u m b e ro fi s o l a t e dv e r t i c e ss a t i s f y i n g ( 付) = ef ( e ) ；0i se x a c t l yd ，t h e ng i saf r a c t i o n a ld e f e c t dm a t c h i n go fg o b v i o u s l ya f r a c t i o n a ld e f e c t - 0m a t c t 她i saf r a c t i o n a lp e r f e c tm a t c h i n g t h e o r e m5 1 9l e tgb eng r a p ha n ddb ean o n n e g a t i v ei n t e g e rw i t h0 d i y ( g ) i 一2 ，gh a saf r a c t i o n a ld e f e c t - dm a t c h i n g 矿a n do n l yi y i ( a s ) i s i + d 加ra n ys y ( g ) m o r e o v e rf y ( g ) i 兰d ( r o o d 2 ) 矿gi sab i p a r t i t eg r a p h t h e o r e m5 1 1 0l e tgb eag r a p ha n gdb ean o n n e g a t i v ei n t e g e rw i t h0 d i y ( g ) f 一2 f ft ( a ) 学，t h e ngh a s 口f r a c t i o n a ld e f e c t - dm a t c h i n g l e tgb eag r a p ha n d7 , ，自，db en o n - n e g a t i v ei n t e g e r sw i t hn + 3 k + d i y ( g ) 卜2 l e tgb eag r a p hw i t ham a t c h i n go fs i z e 七f o ram a t c h i n gm o fs i z eko fg ，i ft h e r e e x i s t s8f r a c t i o n a lm a t c h i n gg c o n t a i n i n gma n dh ( e ) = 1f o re e ( m ) ，t h e ng i s c a l l e df r a c t i o n a lk e x t e n d a b l e w ea l s os a yt h a tm c a nb ee x t e n d e dt oaf r a c t i o n a l p e r f e c tm a t c h i n go fg i fd e l e t i n ga n yn v e r t i c e so fgt h er e m a i n i n gs u b g r a p hg h a s ak - m a t c h i n ga n de v e r y 矗m a t c h i n gc a nb ee x t e n d e dt oaf r a c t i o n a ld e f e c t dm a t c h i n g ， t h e ngi saf r a c t i o n a l ( 扎，k ，d ) - g r a p h i nt h ef o l l o w i n gw ea l w a y ss u p p o s et h a tn ，k ，d x v l s o m er e s u l t so nf a c t o r sa n df r a c t i o n a lf a c t o r so fg r a p h s s a t i s f yn + 3 k + d 茎j y ( g ) 1 2 a tf i r s tw eg i v eac h a r a c t e r i z a t i o no faf r a c t i o n a l ( n ，d ) 一g r a p h t h e o r e m5 2 1ag r a p hgi saf r a c t i o n a lf n ，d j g r a p h 妒a n do n l y 叮t h ef o f - l o w i n gc o n d i t i o n sh o l d ( i ) f o ra n y s v ( a ) a n d l s i2 n ，t h e n i ( a s ) i s l 一礼+ d ( i i ) f o ra n ys v ( c ) s u c ht h a ti s l n + 2 ka n dg 【s c o n t a i n sak - m a t c h i n g ， t h e n t ( g s ) i s i n 一2 k + d t h e o r e m5 2 4e v e r yf r a c t i o n a lm ，k ，鲫一g r a p hgi sa l s oaf r a c t i o n a lm ，k ，圳- g r a p h , w h e r e0s 佗7 n ，0 s 七 w ea l s oi n v e s t i g a t et h ee f f e c to n ( n ，d ) 一g r a p hb yd e l e t i n ga l le d g e t h e o r e m 5 2 7 可g 拈a f r a c t i o n a lm ，k ，d ，一g r a p h ，t h e n f o ra n ye e ( g ) ，g e i s f r a c t i o n a lm 一1 ，七，d + 1 j g r a p h w eh a v ea n o t h e rp r o p e r t yo nf r a c t i o n a l ( n ，k ，d ) 一g r a p h ，w h e nn = 0 i td o e s n t h o l d f o rn 0 t h e o r e m5 2 8g r a p hgi saf r a c t i o n a l ( 七，d ) 一g r a p h 矿a n do n l y 矿f o ra n ym a t c h i n gmo fs i z ei ，t h eg r a p hg v ( m ) i saf r a c t i o n a l ( 一i ，d ) 一g r a p h i nt h et h i r ds e c t i o no fc h a p t e r5 ，w ed i s c u s st h es u f f i c i e n tc o n d i t i o n sr e l a t e dt o c o n n e