（应用数学专业论文）一致星因子图与笼的连通性.pdf

摘要 摘要 1 9 4 0 年，t u r i n 首先将极图理论作为一个学科来研究，p a u le r d s s 进而推动 了这一理论的发展。自此，极图理论成为图论的一个重要分支。在极图理论 里，我们所感兴趣的是图的各种不变量之间的关系，这些不变量包括顶点数、 边数、连通度、最小度、直径等。此外，多大的这些不变量才能保证图具有某 些性质，这也是我们所感兴趣的地方。通常对一类图澎，给定性质汐和一个不 变量p ，我们希望确定出最小的值m ，使得形中每个满足肛( g ) m 的图g 都具 有性质汐。我们称彤中的那些不具有性质汐且肛( g ) = m 的图g 为此问题下的 极图。举个例子，每个顶点数为礼，边数至少为竹的图一定包含圈，那么在这个 问题下的极图就是所有顶点数为他的树。说到这里，我们需要强调下，本文中 所说的极图理论是指广义的，它可以包括各种结构性结果。 在本文中，我们主要讨论了两类极图。 另一类则是关于笼的连通性。在第一章中， 关问题的历史背景。 一类是关于一致星冈子图的刻画， 我们将会介绍一些基本的定义和相 我们称同构于k 1 m 的树为星，这里佗1 。如果图g 的某个生成子图的 所有分支都足星，则称这个生成子图足图g 的一个星冈子。图g 的边赋权 函数是指w ：e ( g ) 一n + ，这里n + 表示正整数集合。设日是图g 的一个 子图，在g 的边赋权函数w 下，图日上所有边的权和称为日的权，也就是 说，w ( h ) = 。e ( 日) 伽( e ) 。如果图g 存在一个边赋权函数w ，使得g 的每个 星因子的权都相等，那么我们则称图g 是一致星因子图。一致星冈予图的 概念是由h a r t n e l l s h r a 在文2 4 1 中提出的。在第二章里，我们首先用g a u 缸 e d m o n d s 匹配结构定理给出在常函数边赋权条件下，所有一致星因子图的完整 刻而；然后给出在一般边赋权函数条件下，所有围长至少为5 的一致星冈予图 的一个清晰刻画。 如果一个缸正则图g 的围长为g ，则称它为( 七，9 ) 一图。对给定的k 和g ，含有 最少顶点数的( 七，9 ) 图则称之为笼。笼问题是图沦中最古老的问题之一。笼 是由t u t t e 5 2 1 在1 9 4 7 提出的，此后得到广泛地研究，然而这个课题太难了。一 般来说，当k 3 ，g 5 时，即使是估计笼的顶点数的界都是很困难的。因 此，最近很多学者把精力放在对笼的结构性质研究上了，比如笼的连通性。在 文章 f 、u ，h u a n ga n dr o d g e r ，c o n n e c t i v i t yo fc a g e s ，j g r a p ht h e o r y , 2 4 ( 1 9 9 7 ) ， i 摘要 1 8 7 - 1 9 1 中，他们猜想在七3 时，所有( 七，9 ) 一笼都是忌连通的。在第三章里，我 们将在前人研究的基础上，继续研究笼的连通性。 关键词：星因子，边赋权，g a l l a i e d m o n d s 分解，临界因子，控制数，匹配 数，笼，围长，连通性 a b s t r a c t a b s t r a c t e x t r e m a lg r a p ht h e o r y , i ni t ss t r i c t e s ts e n s e ，i sab r a n c ho fg r a p ht h e o r y d e v e l o p e da n dl o v e db yh u n g a r i a n s i t ss t u d y , a sas u b j e c ti ni t so w nr i g h t ，w a s i n i t i a t e db yt u r 五ni n1 9 4 0 ，a n dt h em a i ne x p o n e n th a sb e e np a u le r d s sw h oh a s v i r t u a l l yc r e a t e dt h es u b j e c t i ne x t r e m a lg r a p ht h e o r yo n ei si n t e r e s t e di nt h e r e l a t i o n sb e t w e e nt h ev a r i o u sg r a p hi n v a r i a n t s ，s u c ha so r d e r ，s i z e ，c o n n e c t i v i t y , m i n i m u md e g r e e ，d i a m e t e ra n ds oo n w ea r ea l s oi n t e r e s t e di nt h ev a l u e so f t h e s ei n v a f i a n t sw h i c he n s u r et h a tt h eg r a p hh a sc e r t a i np r o p e r t i e s o f t e n ，g i v e n ap r o p e r t y 汐a n da ni n v a r i a n tj uf o rac l a s s 嚣o fg r a p h s 、w ew i s ht od e t e r m i n e t h el e a s tv a l u emf o rw h i c he v e r yg r a p hgi n 澎w i t hp ( g ) mh a sp r o p e r t y 汐 t h o s eg r 印h sgi n 澎w i t h o u tt h ep r o p e r t y 汐a n dw i t hp ( g ) = ma r ec a l l e dt h e e x t r e m a lg r a p h sf o rt h ep r o b l e m f o ri n s t a n c e e v e r yg r a p ho fo r d e r 佗a n ds i z ea t l e a s t 礼c o n t a i n sac y c l e ，a n dt h ee x t r e m a lg r 印h sa r et h et r e e so fo r d e r 扎h a v i n g s a i dt h i s ，ie m p h a s i z et h a ti nt h i st h e s i se x t r e m a lg r a p ht h e o r yi si n t e r p r e t e di n ab r o a d e rs e n s e ，i n c l u d i n gi ni t ss c o p ev a r i o u ss t r u c t u r a lr e s u l t s t w oe x t r e m a lp r o b l e m sa r es t u d i e di nt h i st h e s i s o n ei ss t a r - u n i f o r mg r a p h s ， a n dt h eo t h e ro n ei sa b o u tc a g e s s o m eb a s i cd e f i n i t i o n sa n dt h eh i s t o r yo ft h e r e l a t e dt o p i c sa r ei n t r o d u c e di nc h a p t e r1 as t a ri sat r e ei s o m o r p h i ct ok 1 nf o rs o m en 1 as t a r - f a c t o ro fag r a p h gi sas p a n n i n gs u b g r a p ho fgs u c ht h a te a c hc o m p o n e n to fw h i c hi sas t a r a n e e w e i g h t i n go fg i saf u n c t i o nt ，：e ( g ) 叫n + ，w h e r en + i st h es e to fa l l p o s i t i v ei n t e g e r s f o ras u b g r a p hh ，t h ew e i g h to fh u n d e rwi st h es u mo fa l l t h ew e i g h tv a l u e sf o re d g e sb e l o n g i n gt oh ，i e ，w ( h ) = e e e e ( t t ) w ( e ) ag r a p h g i sc a l l e ds t a r - u n i f o r mi ft h e r ei sa ne d g e - w e i g h t i n gwo fgs u c ht h a te v e r ys t a r - f a c t o ro fgh a st h es a m ew e i g h tu n d e rw h a r t n e l la n dr a l l 2 4 p o s e da no p e n p r o b l e mt oc h a r a c t e r i z ea l lt h es t a r - u n i f o r mg r a p h s i nc h a p t e r2 ，w eu s eg a l l a i - e d m o n d sm a t c h i n gs t r u c t u r et h e o r e mt og i v eac o m p l e t ec h a r a c t e r i z a t i o no fa l l t h es t a r - u n i f o r mg r a p h su n d e rac o n s t a n te d g e - w e i g h t i n gf u n c t i o n s u b s e q u e n t l y , a l lt h es t a r - u n i f o r mg r 印h so fg i r t ha tl e a s tf i v ea r ec h a r a c t e r i z e du n d e rag e n e r a l e d g e - w e i g h t i n gf u n c t i o n i i i a b s t r a c t _ 一一 a k - r e g u l a rg r a p hw i t hg i r t h9i sc a u e da ( 恐，9 ) 一g r a p h 。a ( k ，9 ) 。c a g ei sa ( k ，9 ) 。 g r a p hw i t ht h ef e w e s tn u m b e ro fv e r t i c e sf o rg i v e nka n dg c a g ep r o b l e m i so n e o ft h eo l d e s tp r o b l e m si ng r a p ht h e o r y c a g e sw e r ei n t r o d u c e db yt u t t e 5 2 i n 1 9 4 7 ，a n dh a v eb e e ne x t e n s i v e l ys t u d i e d h o w e v e r ，t h i st o p i ci sv e r yc h a l l e n g i n g ； e v e nt oe s t i m a t et h eb o u n d so nt h eo r d e ro fa ( k ，9 ) 一c a g ei sv e r yd i f f i c u l tf o r 七3 a n d9 5 r e c e n t l y , m a n yr e s e a r c h e r sp a ya t t e n t i o nt ot h es t r u c t u r a lp r o p e r t i e s o fc a g e s f o ri n s t a n c e ，c o n n e c t i v i t y i np a r t i c u l a r ，i th a sb e e nc o n j e c t u r e d f u ， h u a n ga n dr o d g e r ，c o n n e c t i v i t yo fc a g e s ，j g r a p ht h e o r y , 2 4 ( 1 9 9 7 ) ，1 8 7 - 1 9 1 】 t h a ta l l ( k ，9 ) c a g e sa r ek - c o n n e c t e df o re v e r yk 3 i nc h a p t e r3 ，b a s e do i l k n o w nr e s u l t s ，w ew i l lp r o c e e dt ow o r ko nt h ec o n n e c t i v i t yo fc a g e s k e yw o r d s ：s t a r - f a c t o r ，e d g e - w e i g h t i n g ，g a l l a i - e d m o n d sd e c o m p o s i t i o n ，f a c t o r - c r i t i c a l ，d o m i n a t i o nn u m b e r ，m a t c h i n gn u m b e r ，c a g e s ，g i r t h ，c o n n e c t i v i t y i v 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、己公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：多捌l 1 引眵日 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：失殳 ! 誓艘三 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年 月日 各密级的最长保密年限及书写格式规定如下： j _ h _ w h h ? “ _ h _ h h _ t _ * h h “h _ 一r 一 ：内部5 年( 最长5 年，可少于5 年) ：秘密 k l o 年( 最长l o 年，可少于l o 年) ：机密 k 2 0 年( 最长2 0 年，可少于2 0 年) l 。，+ ，。j 。? ? 。j ； c h a p t e r1 i n t r o d u c t i o n c h a p t e r1 i n t r o d u c t i o n 1 1n o t a t i o n sa n dt e r m i n o l o g y t h r o u g h o u tt h i st h e s i s ，w ec o n s i d e ru n d i r e c t e d ，f i n i t ea n ds i m p l eg r a p h s o n l y , w h i c hh a v en e r h e rl o o p sn o rm u l t i p l ee d g e s u n l e s so t h e r w i s ed e f i n e d ，w e f o l l o w 【1 0 ， 11 a n d 【3 9 f o rt e r m i n o l o g ya n dd e f i n i t i o n s l e tg = ( v e ) b eag r a p hw i t hv e r t e xs e tv ( c ) a n de d g es e te ( g ) t h e o r d e ra n dt h es i z eo fga x ed e n o t e db yi y ( g ) la n dl i e ( c ) i i ，r e s p e c t i v e l y i fgi s n o taf o r e s t ，t h e nt h el e n g t ho ft h es h o r t e s tc y c l ei ngi sc a l l e dt h eg i r t ho fg ， d e n o t e db yg ( c ) a n daf o r e s ti sc o n s i d e r e dt oh a v ei n f i n i t eg i r t h w ed e n o t eb y i s o ( g ) t h es e to fi s o l a t e dv e r t i c e so fg ，a n db ye n d ( g ) t h es e to fe n d - v e r t i c e s ( i e ，v e r t i c e so fd e g r e eo n e ) o fg a ne n d - v e r t e xi sa l s oc a l l e dal e a i fg i sat r e e a ne d g ei n c i d e n tw i t ha ne n d - v e r t e xi sc a l l e dap e n d a n te 句e av e r t e xa d j a c e n t t oa ne n d - v e r t e xi sc a l l e das t e m ，a n ds t e m ( g ) d e n o t e st h es e to fs t e m so fg i f scy ( g ) ，t h e ng s = a i r s i st h es u b g r a p ho fgo b t a i n e db yd e l e t i n g t h ev e r t i c e si nsa n da l le d g e si n c i d e n tw i t ht h e m s i m i l a r l y , i fe ce ( g ) ，t h e n g r a p hg e 7i sw i t hv e r t e xs e tv ( g ) a n de d g es e te ( g ) 一e 7 w ed e n o t et h e d e g r e eo fav e r t e xz i ng b yd c ( z ) ，a n dt h es e to fv e r t i c e sa d j a c e n tt ozi ngb y g ( z ) t h em i n i m u md e g r e eo fav e r t e xi ng i sd e n o t e db y6 ( g ) ac y c l e ( o r p a t h ) w i t hn v e r t i c e si sd e n o t e db yg ( o rr ) i fv e r t i c e sua n dva x ec o n n e c t e d i 1 1 g ，t h ed i s t a n c eb e t w e e n 札a n dvi ng ，d g ( u ，u ) ，i st h el e n g t ho fas h o r t e s t ( ，秒) - p a t hi ng f o rv e r t e xs e t s 乃，t 2 y ( g ) ，e ( 正，噩) i st h es e to fe d g e s c h a p t e r1 i n t r o d u c t i o n b e t w e e n 乃a n dt 2 ，a n dd ( t 1 ，t 2 ) = d g ( t 1 ，t 2 ) = m i n d ( t l ，t 2 ) it l 乃，t 2 疋) d e n o t e st h ed i s t a n c eb e t w e e nt 1a n dt 2 t h ed i a m e t e ro fgi st h em a 对删l i i 】 d i s t a n c eo v e ra l lp a i r so fv e r t i c e si ng t h es e to fv e r t i c e sw h i c ha r ea td i s t a n c e7 t osi ngi sd e n o t e db y r ( s ) = 【u v ( c ) jd ( v ，s ) = r ) ，w h e r eri sa ni n t e g e r w ew r i t en ( s ) i n s t e a do f 1 ( s ) t h eg r e a t e s ti n t e g e rl e s st h a no re q u a lt ozi s d e n o t e db yh a n d 一【一z ji sd e n o t e db yk 1 1 2p r o b l e m s p r o b l e m1 ：s t a r - f a c t o r s a n db a c k g r o u n d s as t a ri sat r e ei s o m o r p h i ct ok 1 ，nf o rs o m en 1 w h e nn22 ，t h ev e r t e x o fd e g r e e 礼i nas t a rk 1 ，ni sc a l l e dt h ec e n t e r , a n do n l yo n ev e r t e xi nk 1 1c a n b ec a l l e dt h ec e n t e r as t a r - f a c t o ro fag r a p hgi sas p a n n i n gs u b g r a p ho fg s u c ht h a te a c hc o m p o n e n to fw h i c hi sas t a r ，i e ，a g l ，1 ，跹，2 ，虬。3 - f a c t o r c l e a r l yag r a p hw i t hi s o l a t e dv e r t i c e sh a sn os t a r - f a c t o r i ti sn o th a r dt os e e t h a te v e r yg r a p hw i t h o u ti s o l a t e dv e r t i c e sa d m i t sas t a r - f a c t o r i fo n el i m i t st h e s i z eo ft h es t a ru s e d ，t h ee x i s t e n c eo fs u c has t a r - f a c t o ri sn o n - t r i v i a l ( a ) ( b ) f i g u r e1 1 ( a ) a k 1 ，1 ，k 1 ，2 ，k 1 ，3 ) - f a c t o r ( b ) n o k 1 ，1 ，k 1 ，2 ，k 1 , 3 ) f a c t o r a sa ne x a m p l e ，c o n s i d e rt h eg r a p h si nf i g u r e1 1 t h ef i r s tg r a p hc o n t a i n sa k 1 1 ，k 1 ，2 ，k 1 ，3 ) 一f a c t o r ( s e ef i g u r e1 1 ( a ) ) ，a n dt h es e c o n do n ed o e sn o tc o n t a i n k 1 ，1 ，k 1 ，2 ，k 1 ，3 一f a c t o r ( s e ef i g u r e1 1 ( b ) ) f o rag r a p hg ，w ed e n o t ei ( g ) t h en u m b e ro fi s o l a t e dv e r t i c e si ng a n 2 i n d e p e n d e n ts e ts v ( g ) m e a 4 - 1 sa l lt h ev e r t i c e si nt h es u b g r a p hg 司a r ei s o l a t e d v e r t i c e s t h ef i r s tr e s u l to fs t a r - f a c t o r sw a s g i v e nb ya k i y a m a ，a v i sa n de r a 【1 1 t h e yp r o v e dt h a tag r a p hgh a sa k 1 ，1 ，k 1 ，2 ) 一f a c t o ri fa n do n l yf fi ( g s ) 2 i s i f o re v e r yscy ( g ) s u b s e q u e n t l y , a m a h a s h ia n dk a n o 2 】a n dl a s v e r g n a s 3 1 1 ， i n d e p e n d e n t l y , p r e s e n t e dac r i t e r i o nf o rt h ee x i s t e n c eo far e s t r i c t e ds t a r f a c t o r i e ， k l 1 i 1 一，k 1 ，t l f a c t o r t h e o r e ml 1 ( a m a h a s h ia n d k a n o 【2 】；l a sv e r g n a s 3 1 ) l e tg b e 口g r a p ha n d n 2b ea ni n t e g e r t h e n 现ef o l l o w i n gs t a t e m e n t sa r ee q u i v a l e n t ： 1 gh a sa k 1 1 i 1 一，k 1 ，n ) - f a c t o r ； 2 i ( g s ) h i s l o ra n ys u b s e ts y ( g ) j 3 i g ( 矿) i ( 1 n ) l u l o ra n yi n d e p e n d e n ts e tu y ( g ) t h e r ee x i s tn u m e r o u sr e s u l t so nf a c t o r si n c l u d i n go re x c l u d i n gg i v e ne d g e s c h e n ，e g a w aa n dk a n o 1 3 】g a v eas u 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 k 1 ，1 i 1 ，甄，n ) - f a c t o rw h i c hc o n t a i n sa na r b i t r a r yg i v e ne d g e t h e o r e m1 2 ( c h e n ，e g a w aa n dk a n o 【1 3 1 ) l e tg b eag r a p ha n d 佗2b eo n i n t e g e r t h e nt h ef o l l o w i n gt w os t a t e m e n t sa r ee q u i v a l e n t ： ( i ) e v e r ye 曲eeo gp o s s e s s e s 饶ep r o p e r t yt h a ts o m e k l ，l ，k 1 ，n - f a c t o r o ygh a soc o m p o n e n tw h i c hi si s o m o r p h i ct ok 1 ，1o rk 1 ，2a n dc o n t a i n se j ( i i ) 1 0 ra l lscy ( g ) ，w eh a v e w h e r e t ( g s ) h i s i 一， f2 礼一1 = l0 矿g 司c o n t a i n sa ne d g e ， o t h e r w i s e t h ea u t h o r sa l s og a v ea ne x a m p l et os h o wt h a tc o n d i t i o ni ( g s ) i nt h e o r e m1 2w a sb e s tp o s s i b l ef o re v e r yi n t e g e r 佗2 h i s i 一 i fag r a p hgh a sn o k 1 l ，1 一，k l ，n ) 一f a c t o r ，t h e ng h a sav e r t e xs u b s e ts s u c ht h a ti ( a s ) n i s lb yt h e o r e m1 1 w ec a l ls u c ha s e tsab a r r i e rs e t 3 c h a p t e r1 i n t r o d u c t i o n 0 fg f o r k 1 ，1 i - 1，k 1 n 卜f a c t o r s s o m er e s u l t so nb a r r i e rs e t sw e r eo b t a i n e d i n 【6 3 y u 6 2 ，6 4 ，6 5 】a l s os t u d i e dt h es t r u c t u r eo fg r a p h sw i t hau n i q u es t a r - f a c t o ra n df o u n da1 0 w e rb o u n df o rt h en u m b e ro fs t a r - f a c t o r si nag r a p h a k 1 ，1 1 一，髓，n ) - f a c t o ri sp r o p e ri fo n eo fi t sc o m p o n e n t si si s o m o r p h i ct ok 1 巾 g i v e nna n dn 2w ed e n o t eb y ( ，礼) t h em a x i m u mn u m b e ro fe d g e si na g r a p ho fo r d e rnw h i c hh a sap r o p e ru n i q u e k 1 ，1 ，甄，竹】一f a c t o r h e n c ef o r a n yg r a p hgo fo r d e rnw h i c hh a sap r o p e ru n i q u e k 1 ，1 1 ，n ) f a c t o rw e h a v ei e ( g ) f ( ，佗) t h e o r e m1 3 ( y u 6 2 ) l e tn 2 巧ag r a p hg o yo r d e rnh a sap r o p e ru n i q u e k 1 1 ，1 一，甄，n ) - f a c t o r ，t h e n e ( n ，礼) = 掣+ 1 6 ( 丛= 1 2 f 丝型 。 业掣+ 1 8 盟掣+ 1 8 上 盟f 丝型 8 ( n - n ) 2 - 9 + n 8 ( n - - n ) ( 。n - n - - 2 ) + n 8 礼= 2a n dn 三0 2 n = 2a n dn 三1 n = 3a n dn 兰1 n = 3a n dn 三3 ( m o d3 ) ， m o d 3 ) ， m o d4 ) ， m o d4 ) ， n = 3a n dni se v e n 仡4a n dn n ( m o d2 ) ， 扎4a n dn 三n ( m o d2 ) h e r ew eg i v eag e n e r a l i z a t i o no fs t a r - f a c t o r s ad o u b l e s t a ri sat r e eo fo r d e r a tl e a s tf o u ra n dh a so n l yt w oa d j a c e n tv e r t i c e so fd e g r e ea tl e a s tt w o i no t h e r w o r d s ，ad o u b l es t a ri so b t a i n e db yc o n n e c t i n gt h ec e n t e r so ft w os t a r s ad o u b l e s t a r - f a c t o ro fag r a p hg i sas p a n n i n gs u b g r a p ho fgs u c ht h a te a c hc o m p o n e n t o fw h i c hi sad o u b l e - s t a r w i t ht h i sd e f i n i t i o n ，i ti sn a t u r ea n di n t e r e s t i n gt o c o n s i d e rt h ef o l l o w i n gp r o b l e m ： p r o b l e m1 1 i st h e r eac r i t e r i o ny o rat r e et oh a v ead o u b l e s t a r - f a c t o r ? ( i i ) i st h e r eac r i t e r i o ny o rat r e eh a v i n gad o u b l e s t a r - f a c t o rt oh a v ep r e c i s e l y o n ed o u b l e s t a r - f a c t o r ? ( 沈) i st h e r eac r i t e r i o ny o rat r e eh a v i n gad o u b l e s t a r - f a c t o rt oh a v ed o u b l e s t a r - f a c t o r sw i t ht h ec o n s t a n tn u m b e r0 | c o m p o n e n t s ? 4 矿矿矿矿矿矿矿 c h a p t e r1 i n t r o d u c t i o n 3 7 】 s o m eo t h e rr e l a t e dr e s u l t so ns t a r - f a c t o r sc a nb ef o u n di n 【8 ，1 2 ，1 3 ，1 6 ，2 2 ，3 0 ， a ne e w e i g h t i n go fag r a p hg i saf u n c t i o nw ：e ( a ) - - - - - 4n + ，w h e r en + i s t h es e to fa l lp o s i t i v ei n t e g e r s f o ras u b g r a p hh ，t h ew e i g h to fhu n d e rwi st h e s u mo fa l lt h ew e i g h tv a l u e sf o re d g e sb e l o n g i n gt oh ，i e ，w ( h ) = e e e ( 日) 切( e ) m o t i v a t e db yt h em i n i m u mc o s ts p a n n i n gt r e ea n dt h eo p t i m a la s s i g n m e n tp r o b - l e m s ，h a r t n e l la n dr a l l 【2 4 p o s e dt h ef o l l o w i n gi n t e r e s t i n gp r o b l e m s t a r - w e i g h t i n gp r o b l e m ( h a r t n e l la n dr a i l 2 4 ) ：f o rag i v e ng r a p hg ，i s t h e r ea ne d g e - w e i g h t i n gwo fgs u c ht h a te v e r ys t a r - f a c t o ro fgh a st h es a m e w e i g h tu n d e r 伽? a g r a p hgi sc a l l e ds t a r - u n i f o 仃ni ft h e r ei sa ne d g e - w e i g h t i n gwo fgs u c h t h a te v e r ys t a r - f a c t o ro fgh a st h es a m ew e i g h tu n d e r 叫t os t a r tt h ei n v e s t i g a - t i o n ，o n em a yc o n s i d e rt h a tt h es p e c i a lc a s et h a twi sac o n s t a n te d g e - w e i g h t i n g f u n c t i o n ，i e ，a l le d g e si ng a r ea s s i g n e dw i t ht h es a h l ew e i g h t i nc h a p t e r2 ， w ef i r s t l yu s eg a l l a i - e d m o n d sm a t c h i n gs t r u c t u r et h e o r e mt og i v eac o m p l e t e c h a r a c t e r i z a t i o no fa l lt h es t a r - u n i f o r mg r a p h su n d e rt h ec o n s t a n te d g e - w e i g h t i n g f u n c t i o n s u b s e q u e n t l y , a l lt h es t a r - u n i f o r mg r a p h so fg i r t ha tl e a s tf i v ea r ec h a r - a c t e r i z e df o rag e n e r a le d g e - w e i g h t i n gf u n c t i o n p r o b l e m2 ：c a g e s a k - r e g u l a rg r a p hw i t hg i r t hgi sc a l l e da ( k ，9 ) - g r a p h a ( 七，9 ) 一c a g ei sa ( k ，9 ) 一 g r a p hw i t ht h