（运筹学与控制论专业论文）图的因子与分数因子.pdf

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 图的因子与分数因子 禹继国 ( 山东大学数学与系统科学学院，济南2 5 0 1 0 0 ) ( 指导教师：刘桂真教授) 中文摘要 图论在二十世纪经历了空前的发展，致使发展的一个主要原因是图论在其 他学科诸如物理学、化学、心理学和社会学的应用，另一个原因是许多理论计 算机科学的问题可以转化为图论的问题本文我们主要研究图的因子与分数因 子因子理论是图论中的一个重要分支，它有着非常广泛的应用 本文中所考虑的图均为无向简单图令g 是一个具有顶点集y ( g ) ，边集 e ( g ) 的n 阶图对口y ( g ) ， 在g 中的度用d a ( 口) 表示我们用n a ( v ) 表示 在g 中与”相邻的顶点集，n a v 表示g a ( ”) 1 3 ”) 如果s 是w ( a ) 的一个子 集：为了方便，我们用d g ) 代替。s 如( 。) 用g s 1 表示由s 导出的g 的子 图若n v ( a ) s ，则我们用e a ( u ，s ) 表示连接u 和s 中的一点的边的个数若 t v ( a ) s ，则我们用c a ( t , s ) 代替。f r e g ( u ，s ) 若s y ( g ) ，则只( g s ) 表 示在g s 中具有度i 的顶点集且1 只( g s ) | = p i ( g s ) 有时，我们用i ( c s ) 来代替p 0 ( g s ) ，用( g s ) 代替p o ( g s ) 令9 和，是定义在v ( g ) 上的两个整数值函数，使得对任意的z v ( a ) 都有 。墨9 ( z ) s ，( z ) g 的一个( 9 ，) 因子f 是g 的一个生成子图使得9 ( z ) sd f ( x ) s ，( z ) 对所有z v ( g ) 成立若9 ( z ) = ，( z ) 对所有的z v ( g ) 成立，则一个( g ，) 一 因子称为一个，- 因子若，( z ) = 对某个非负整数和所有z v ( a ) 成立，则一 个，- 因子称为一个k 因子一个分数( g ，) 示性函数是一个函数h ，它分配给图g 的每条边一个在【0 ，1 】中的数，使得对每个顶点。v ( g ) 都有g ( z ) d g ( z ) ，( 。) ， 其中d g 、( ) = 。e ， ( e ) 是的分数度且b = e ：e = v e ( g ) 令h 是图g 的一个分数( 9 ，) - 示性函数，置e h = e ：e e ( g ) 且h ( e ) o 若g 是图g 的 一个生成子图使得e ( a h ) = e h ，则g 称为g 的一个分数( g ，) 因子当9 ( x ) = 0 且，( z ) = 1 对所有的。v ( a ) 成立时，则这个分数示性函数就是一个分数匹配 的示性函数当9 ( z ) = ( x ) = 1 对所有的v ( a ) 成立时，则这个示性函数是 一个分数完美匹配，即一个分数1 因子的示性函数若g ( x ) = ，( z ) = k ，则一个 分数( g ，) 因子称为一个分数k 因子 1 8 9 1 年。j p e t e r s o n 在他的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 成边不相交的2 因子的并他同时也证明了每个2 ，连通3 正则图有一个1 因 子这两个结果被认为是现代图因子理论研究的开始为了将匹配理论从偶图 推广至一般图，t u t t e 于1 9 4 7 在他的l 一因子定理中给出了一个图有1 一因子的判 定准则这个完美的定理或许是因子理论中最基础的结果在1 9 5 2 年，t u t t e 又在他的，因子定理中给出一个图有，一因子的判定准则，从而推广了上面的 结果l o v 如z 在1 9 7 0 年得到了一个图有( g ，) 因子的一个充分必要条件，并于 1 9 7 2 年给出了一个图有奇偶( g ，) 因子的一个充分必要条件从那时起，关于 因子的大量结果不断地涌现出来 因子理论研究主要关注以下几个方面：( 1 ) 图有因子的充分条件；( 2 ) 具有 特殊性质的因子如含有某些边且不含有另外某些边的因子，最大最小因子和连 通因子等；( 3 ) 匹配扩张及其应用；( 4 ) 因子临界性；( 5 ) 图的因子分解；( 6 ) 因 子、因子分解、匹配扩张和因子临界性相互问的关系所使用的工具主要是图 的各种参数如最小度、度和、韧度、联结数、邻域并和闭包等 分数图论是相对年轻的一个分支关于这方面的第一本专著是由c l a u d e b e r g e 在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 ，) 奇因子一个充分必要条件第四章考虑( m g ，m r ) 图中的( g ，) 因子第五章我 们研究图的连通因子我们得到了2 连通无爪图的有连通因子的一个充分条 件，也得到了无爪图有分数l 一因子的一个充分条件第六章我们集中给出关于 因子的一些可进一步研究的问题和猜想，其中大部分是本文的后继工作这些 问题和猜想对因子理论研究将起到积极的推动作用 下面列出本文的主要结果 d r w o o d a l l 给出了图的联结数的概念，它定义为： 。，y 、 b i n d ( c ) = r a i n = 群：o x cv ( g ) ，g ( x ) v ( g ) ) 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 a n d e r s o n 给出了一个图有1 一因子的一个联结数条件，我们得到了一个图有分数 1 一因子的关于联结数的充分必要条件 结论1 令g 是一个图则g 有分数1 因子当且仅当b i n d ( g ) 1 pk a t e r i n i s 和w o o d a l l 研究了图的k 因子的联结数条件我们给出了一个 图有分数k 一因子的与联结数和最小度相关的充分条件 结论2 令g 是一个n 阶图，2 若下列条件之一成立，则g 有一个分 数k ，因子 ( a ) k n 是偶数n 4 k + 1 4 v k + 2 ， i n ( x ) l 坠掣 对v ( a ) 的所有非空独立子集x 都成立且 粥) 警# ： ( b ) k n 是奇数n 4 k + l 一4 切i 1 ， | ( 驯2 坠掣 对v ( a ) 的所有非空独立子集x 都成立且 们) 坠掣 对于度条件，我们给出了下面的主要结论 结论3 令k 是一个整数满足1 ，且令g 是一个连通的n 阶图满足 n2 4 k 一3 ，d ( g ) 女若m a x d g ( “) ，d a ( v ) i n 对g 的每一对不相邻的顶点u ，” 都成立，则g 有一个分数因子， 令g 是一个图”，”v ( a ) 是g 中两个不同的顶点，u 和”之间的距离 是连接这两个顶点的最短路所含的边数，用d i s t ( u ，”) 表示称图g 是范型的， 若对g 中满足d i s t ( u ，”) = 2 的每一对顶点都有m a x d a ( u ) ，d g ( ”) ) ；我们考虑 了一个图有分数1 一因子的范型条件，并通过引入k 极小集得到了一个图有分数 一因子的范型条件 结论4 令g 是一个n 阶连通图满足d ( g ) 女，其中是一个正整数且 n 8 k 2 + 1 2 1 ；+ 6 若g 是范型图，则g 有一个分数k 一因子 令，是定义在v ( a ) 上的一个函数使得对每个x v ( g ) 都有l ( z ) 是一个正 奇整数我们用，：v ( c ) - f l ，3 ，5 ，) 表示这个函数g 的一个生成予图f 称 为一个( 1 ，) - 奇一因子如果d f ( z ) 1 ，3 ，5 ，( z ) ) 对所有的z v ( g ) 成立令 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 n 是一个正整数且f ( z ) = 2 n 一1 对所有的f v ( c ) 成立，则一个( 1 ，) 一奇因子 称为g 的一个f 1 ) 3 ，5 ，2 n 1 ) 因子，是定义在v ( c ) 上的一个正奇整数函 数，g 是g 的一个分数( 1 ，) 一因子且d g 。( 。) l ，3 ，5 ，( 。) ) ，贝l jg 称为g 的 一个分数( 1 ，) 奇因子对所有的z 矿( g ) 置f ( x ) = 2 n l ，则一个分数( 1 ，) 一 奇因子就变成了一个分数f 1 ，3 ，5 ，2 n l 因子我们讨论了树和一般图的分 数( 1 ，胁因子 结论5 令g 是一个偶阶树且f ：v ( c ) _ 1 ，3 ，5 ，) 是一个正奇整数值函 数则g 有一个分数( 1 ，) 一奇因子当且仅当对所有z v ( e ) 都有i ( g z ) ，( 。) 结论6 令g 是一个图且f ：v ( g ) - ( 1 ，3 ，5 ，) 是一个正奇整数函数则g 有一个分数( 1 ：，) 一奇因子当且仅当对所有的s v ( c ) 都有t ( g s ) ! ，( s ) 在第五章我们研究了二部( r a g r n ，) 一图中的( g ，) 一因子并推广了l i u 和z a n g 的结果 结论7 令g = ( x ，e ( g ) ) 是一个二部( m g 、m r ) 图且9 和，是定义在 v ( g ) 上的两个正整数值函数使得1s9 ( z ) 曼，( z ) ，g 的边连通度 ( g ) 满足 a ( g ) 2 n 一1 ，f ( x ) = ，( x ) 且g ( x ) = 9 ( y ) 则g 有一个( 9 ，) 因子含有任意给 定的边且不含有任意给定的n 一1 条边 设f 是图g 的一个因子f 称为g 的一个连通因子若f 是连通的连通 因子问题与h a j n i l t o n 问题和信息网络有着密切的联系在第五章我们考虑了2 连通无爪图的连通因子和连通无爪图的分数1 因子 结论8 令g 是一个2 连通的无爪图且n b 是两个整数满足2 。sb 若 g 有一个f n ，卟因子，则g 有一个连通的h6 + l 卜因子 在第六章，我们提出了关于图的因子的一些问题和猜想这些问题和猜想 对于因子理论的进一步研究具有重要的意义 因子 关键词：分数1 一因子；分数- 因子；分数( 1 ，) - 奇因子；( g ，) 因子；连通 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 f 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 y uj i g u o ( s c h o o lo fm a t h & s y s s c i ，s h a n d o n gu n i v ，j i n a n2 5 0 1 0 0 ) a b s t r a c t g r a p ht h e o r yh a sw i t n e s s e da l lu n p r e c e d e n | e dg r o w t hi at h et w e n t i e t hc e n t u r y0 n e o ft h em a i nr e a s o n sf o rt h i sg r o w t hi st h ea p p l i c a b i l i t yo fg r a p ht h e o r yi nm a n yo t h e r d i s c i p l i n e ss u c ha sp h y s i c s ，c h e m i s t r y p s y c h o l o g y ，a n ds o c i o l o g y y e ta n o t h e rr e a s o ni s t h a ts o n i co ft h ep r o b l e m si nt h e o r e t i c a lc o n l p u t e rs c i e n c ec a nb et r a n s f o r m e di n t og r a p h t h e o r e t i c a lp r o b l e m s i nt h i st h e s i sw ep a yo u rm a i na t t e n t i o nt of a c t o r sa n df r a c t i o n a l f a c t o r so fg r a p h s f a c t o rt h e o r yi sa ni m p o r t a n tb r a n c ho fg r a p ht h e o r ya n dh a ss o m e s i g n i f i c a n ta p p l i c a t i o n s a l lg r a p h sc o n s i d e r e da l ef i n i t es i m p l eg r a p h sl e tgb eag r a p ho fo r d e rnw i t h v e r t e xs e tv ( a ) a n d e d g e s e te ( g ) ，f o rav e r t e xu v ( a ) t h e d e g r e eo f ui ngi sd e n o t e d b yd e ( v ) w ew r i t e g ( ) f o rt h ev e r t i c e sa d j a c e n tt o ，a n dn a v f o rn a ( v ) u ”) i f si sas u b s e to fv ( g ) ，f o rc o n v e n i e n c ew ew r i t ed a ( s ) i n s t e a do f sd e ( v ) b ya s 】 w ed e n o t et h es u b g r a p ho fgi n d u c e db ysi f “el j ( g ) s t h e nw ew r i t ee a ( u s ) t o d e n o t et h en u m b e ro fe d g e sj o i n i n gnt oav e r t e xi nsi ft 至v ( a ) s ，t h e nw ew r i t e e c ( t ，s ) i n s t e a do f 。te a ( u ，s ) i fs v ( g ) ：t h e nr ( g s ) d e n o t e st h ev e r t e xs e c i ng sw i t hd e g r e eia n d1 只( g s ) l = n ( g s ) s o m e t i m e s ，w ew r i t e ( g s ) f o r 娲( g s ) a n d i ( a s ) f o rp o ( a s ) l e tga n dfb et w o i n t e g e r v a l u e df u n c t i o n ss u c ht h a t0 g ( x ) f ( x ) f o ra l l 。e 矿( g ) a ( g ，) 一f a c t o rf o fgi sas p a n n i n g s u b g r a p ho fg s u c ht h a t9 扣) d f ( x ) ，( 。) f o ra uz v ( g ) i fg ( ) = = ，( 。) f o rb n2 2 v t c ) ，t h e n 邑( 9 ，) 一f a c t o ri s c a l l e da 1 1 - f a c t o r i f ，( z ) = f o rs o m en o n n e g a t i v ei n t e g e r a n da l l 。矿( g ) ，t h e na nf - f a c t o r i sc a l l e dak - f a c t o r af r a c t i o n a l ( g ，) 一i n d i c a t o rf u n c t i o ni saf u n c t i o nht h a t a s s i g n s t oe a c he d g eo fg r a p hgan u m b e ri n 0 ，1 s ot h a tf o re a c hv e r t e x v ( a ) w eh a v e 9 ( z ) d a h ( t ) ，( z ) ，w h e r ed a ( z ) _ 。e zh ( e ) i st h ef r a c t i o n a ld e g r e eo fzev ( c ) w i t h 玩= e ：e = x y e c c ) l e t hb eaf r a c t i o n a l ( 9 ，) 一i n d i c a t o rf u n c t i o no fa g r a p hg s e te h = e ：e e ( c ) a n dh ( e ) o ) i fg ai sas p a n n i n gs u b g r a p h 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 o fgs u c ht h a te ( c h ) = e h ，t h e ng i sc a l l e daf r a c t i o n a l ( 9 ，) 一f a c t o ro fg w h e n 9 ( 卫) = 0a n d ，扛) 苎1f o ra l l 。y ( g ) ，af r a c t i o n a li n d i c a t o rf u n c t i o ni s a ni n d i c a t o r f u n c t i o no faf r a c t i o n a lm a t c h i n g w h e n9 ( z ) = l ( z ) = 1f o re v e r yz v ( g ) a f r a c t i o n a l ( g ，) i n d i c a t o rf u n c t i o ni s a ni n d i c a t o rf u n c t i o no faf r a c t i o n a lp e r f e c tm a t c h i n g ，t h a t i s af r a c t i o n a l1 - f a c t o r i f9 ( z ) = f ( x ) = 女，t h e naf r a c t i o n a l ( g ，) 一f a c t o ri s c a l l e da f l a ( ：t i o n a l f a c t o r i n1 8 9 1 ，j p e t e r s o n ，i nh i s2 - f a c t o r i z a t i o nt h e o r e m p r o v e dt h a te v e r yg r a p ho f e v e i ld e g r e ec a l lb ed e c o m p o s e di n t ot h ea n i o no fe d g e d i s j o i n t2 - f a c t o r sh ea l s os h o w e d t h a te v e r y2 - c o n n e c t e d3 - r e g u l a rg r a p hh a sa1 - f a c t o r t h e s et w or e s u l t sc a nb ev i e w e d a saf o r e r u n n e ro fm o d e r n g r a p hf a c t o rt h e o r y t oe x t e n dm a t c h i n gt h e o r yf r o mb i p a r t i t e g r a p h st og e n e r a lg r a p h s ( i e n o n - b i p a r t i t eg r a p h s t u t t ei nh i s1 - f a c t o rt h e o r e m o f 1 9 4 7g a v eac r i t e r i o nf o rt h ee x i s t e n c eo f1 - f a c t o r so fag r a p h t h i se l e g a n tt h e o r e mi s p e r h a p st i l em o s tf u n d a m e n t a lr e s u l t i nf a c t o rt h e o r y g e n e r a l i z i n gt h i sr e s u l t ，i nt 9 5 2 t u l l ea g a i ng a v eac r i t e r i o n ，i nh i sf - f a c t o rt h e o r e m ，f o rag r a p ht oh a v eaf - f a c t o r l o v d s zo b t a i n e dan e c e s s a r ya n ds l f f f i c i e n tc o n d i t i o nf o rag r a p ht oh a v ea ( g ，) f a c t o r i n1 9 7 2l o v i s za g a i ng a v eac r i t e r i o nf o rag r a p ht oh a v eap a r i t y ( g ，) 一f a c t o rs i n c e t h e nm l m e r o u sr e s u l t so nf a c t o rt h e o r ys p r u n gf o r t h f a c t o rt h e o r ym a i n l yf o c u s e do nt h ef o l l o w i n g , a s p e c t s ： ( 1 ) s u f f i c i e n tc o n d i t i o n sf o rg r a p h st oh a v ef a c t o r s ；( 2 ) f a c t o r sw i t hp r e s c r i b e dp r o p - e r t i e ss u c ha sf a c t o r i n c l u d i n ga n de x c l u d i n gs o m eg i v e ne d g e s j m a x i m u mf a c t o r so r n z i n i n l u n lf a c t o r sa n dc o n n e c t e df a c t o r s ：( 3 ) m a t c h i n ge x t e n s i o na n di t s g e n e r a l i z a t i o n ； ( 4 ) f a c t o r c r i t i c a l i t y ：( 5 ) f a c t o r i z a t i o no fg r a p h s ；( 6 ) t h er e l a t i o n s h i pa m o n gf a c t o r f a c t o r i z a t i o n m a t c h i n ge x t e n s i o na n df a c t o r c r i t i c a l i t y t h em a i nt o o l sf o ru st os t u d yf a c t o r sa r ea l lk i n d so fp a r a m e t e r so fag r a p hs u c ha 8 m i n i m m n d e g r e e ，d e g r e es u m ，t o u g h n e s s ，b i n d i n gn u m b e r ，n e i g h b o r h o o du n i o n ，c l o s n r e a n ds oo n i h a c t i o n a lg r a p ht h e o r yi sar e l a t i v e l y y o u n g e rb r a n c h t h ef i r s tm o n o g r a p ho i l t h i st o p i cw a sw r i t t e nb yc l a u d eb e r g ei nh i sf r a c t i o n a lg r a p h t h e o r yi n1 9 7 8 i n1 9 9 7 e r s c h e i n e r m a na n dd h u l l m a nw r o t ean e wb o o kc o n c e r n i n gf r a c t i o n a lg r a p h t h e o r yw h i c hc o v e r e dn e a r l ya l lt h em a i nt o p i c ss u c ha sf r a c t i o n a lm a t c h i n g f r a c t i o n a l e d g ec o l o r i n g ，f r a c t i o n a lc o l o r i n g ，f r a c t i o n a la r b o r i c i t ya n df r a c t i o n a li s o m o r p h i s m w e h a v et w op r i n c i p a lm e t h o d st oc o n v e r tg r a p hc o n c e p t sf r o mi n t e g e rt of r a c t i o n a l t h e f i r s ti st of o r m u l a t et h ec o n c e p t sa s i n t e rp r o g r a a n sa n dt h e nt oc o n s i d e rt h el i n e a r p r o g r a m m i n gr e l a x a t i o n t h es e c o n di st om a k eu s eo ft h es u b a d d i t i v i t yl e m m a t h e s e $ 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 t w oa p p r o a c h e st y p i c a l l yy i e l dt h es a m er e s u l t s n e a r l ye v e r yi n t e g e r v a l u e di n v a r i a n t e n c o u n t e r e di naf i r s tc o u r s ei ng r a p ht h e o r yg i v e st oaf r a c t i o n a la n a l o g u e i nt h i st h e s i s w e m a i n l yc o n s i d e rf r a c t i o n a lf a c t o r so fg r a p h sb yu s i n gp u r eg r a p h t h e o r e t i c a la p p r o a c h t h et h e s i si sd i v i d e di n t os i xc h a p t e r sas h o r tb u tr e l a t i v e l yc o m p l e t es u r v e yf o r f a c t o rt h e o r yi sg i v e ni nc h a p t e r1 、t h er e s u l t so ac o n n e c t e df a c t o r sa r en o tc o n t a i n e di n t h e s ec h a p t e ra n dt h e ya r eg i v e ni ns e c t i o no n eo fc h a p t e rf i v e w ed i s c u s st h es u f f i c i e n t c o n d i t i o n sf o rg r a p h st oh a v ef r a c t i o n a lk - f a c t o r si nc h a p t e r2 i nc h a p t e r3w eg i v ea n e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n f o rag r a p ht oh a v eaf r a c t i o n a l ( 1 ，) 一o d d f a c t o r ( g ，) f f a c t o r si nb i p a r t i t e ( m 9 ，m ，) g r a p h sa r ec o n s i d e r e di nc h a p t e r4 w ew i l l ，i nc h a p t e r5 ， s t u d y t h ec o n n e c t e df a c t o r so fg r a p h sc o n n e c t e df a c t o r si n2 - c o n n e c t e dc l a w f l e eg r a p h s a n df r a c t i o n a ll - f a c t o r si nc o n n e c t e dc l a w f l e eg r a p h sa r ec o n s i d e r e d a n di nc h a p t e r6 ， w el i s ts o l n ep r o b l e m sa n dc o n j e c t u r e si nf a c t o rt h e o r ym o s tp r o b l e m sa n dc o n j e c t u r e s a r et h ew o r kt h a tt h ea u t h o rw i l ld o t h e - p l a ya ni m p o r t a n tr o l ei nf u r t h e rs t u d yo f f a c t o rt h e o r yo fg r a p h s n e x t l yw ew i l ll i s tm a i nr e s u l t si nt h i st h e s i s d ，r w o o d a l tg a v et h ec o n c e p to fb i u d l n gt m n l b e rw h i c hi sd e f i n e da s b i n d ( g ) ：m i n 掣：。ni ，( g ) n a ( x ) 矿( g ) ) 1 o i a n d e r s o ng a v eab i n d i n gn u m b e rc o n d i t i o nf o rag r a p ht oh a v ea1 - f a c t o r w eo b t a i na n e c e s s a r ya n ds u 箭c i e n tc o d i t i o nf o rg r a p h st ol l a v ef i a c t i o n a l1 - f a e l o r s ， c o n c l u s i o n1 l e tgb eng r a p h t h e ng ；a s n ! t n c t i o n a ll 一| a c t o r 毽a r z do n l y 啦 6 i d ( g ) 三1 。 p k a t e r i n i sa n dv v b o d a l ls t u d i e dt h eb i n d i n gn u m b e ro fg r a p h sa n dt h ee x i s t e n c e o fk - f a c t o r s w eg i v et w os u f f i c i e n tc o n d i t i o n sf o r g r a p h st oh a v ef r a c t i o n a lk - f a c t o r s c o n c e r n i n g o nb i n d i n gn u m b e ra n dm i n i m u m d e g r e e t h em a i n r e s u l ti ss af o l l o w s c o n c l u s i o n2 。l e tgb eag r a p ho io r d e rnw i t hk 2 1 o n eo | t h e | o l l o w i n 9t w o c o n d i t i o n ji ss a t i s f i e d ，t h e ngh a snf r a c t i o n a l 墒c t o r n ) k ni se v e n n 4 k + 1 4 、k + 2 i n ( x ) i i x l 一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 o ra l ln o n e m p t yi n d e p e n d e n ts u b s e tx 盯v ( g ) a n d 蜩) 警 阳jk r ai so d dn 4 k + 1 4k , v 7 1 n ( x ) l 坠掣 b r a l ln o n e m p t yi n d e p e n d e n ts u b s e txo f ( g 1a n d 胛) 坠掣 f o rd e g r e ec o n d i t i o n s w eh a v et h ef o l l o w i n gr e s u l t c o n c l u s i o n3 l e t b e i n t e g e rw i t hk 1 a n dl e tgb eac o n n e c t e dg r a p ho fo r d e r n i e ，l 4 k 一3 6 ( g ) 岛巧f r 。z d g ( ) d c ( l ，) ) i nl o te a c hp a i ro ，n o n a d j a c e n t u e ，r i c e s “u o g ，t h e ng h a saf r o e t i o n a la 母c t o r l e tgb eag r a p ht h ed i s t a n c eb e t w e e nt w od i f f e r e n tv e r t i c e su ，u v ( a ) i st h e n u l n b e ! o fe d g e so ft h es h o r t e s tp a t hj o i n i n g “a n dva n dd e n o t e db yd i s t ( u ， ) w ew i l l s a yt h a tg i so ff a nt y p e ，i fe v e r yp a i ro fv e r t i c e s v ( g ) w i t hd i s t ( u v ) = 2s a t i s f i e s i i l a x ( f f g ( “) ，d e ( u ) 百n w ec o n s i d e ra f a nt y p ec o n d i t i o nf o rag r a p ht oh a v ef r a c t i o n a l l f a t ：t o r a n daf a nt y p ec o n d i t i o nf o rt h ee x i s t e n c eo ff r a c t i o n a lk - f a c t o r sb yi n t r o d u c i n g t h ec o l l c e p to f 一m i n i m a ls e t ， c o n c l u s i o n4 l e tgb eac o n n e c t e dg r a p ho o r d c ? nw i t ha ( c ) k ，w h e r eki sap o s i f i v ei n t e g e ra n d n 8 k + 1 2 k + 6i jg i so ff a nt y p e t h e ngh a sa 陋c t i o n a lk 一如c t 0 1 1 l e tfb eah m c t i o nd e f i n e do nv ( a ) s u c ht h a tf ( z ) i sap o s i t i v eo d d i n t e g e rf o re v e r y z v ( a ) w e d e n o t es u c ha f u n c t i o nb yf ：v ( g ) _ ( 1 3 5 ，) t h e nas p a n n i n gs u b g r a p hf o f gi sc a l l e da n ( 1 ，) 一o d d f a c t o ri f d f ( z ) 1 ，3 ，5 ，( x ) f o ra l lz v ( g ) l e tnb eap o s i t i v ei n t e g e ra n d ，( ) = 2 n 一1f o ra l lz v ( g ) ，t h e na ( 1 ，) 一o d d f a c t o r i sc a l l e da 1 ，3 ，5 ，2 n 一1 ) 一f a c t o ro fg i sap o s i t i v eo d di n t e g e r v a l u e df u n c t i o n d e f i n e do ny ( g ) ，g i saf r a c t i o n a l ( 1 ，) 一f a c t o ro fga n dd g h ( z ) l ，3