（运筹学与控制论专业论文）on+the+wiener+and+reverse+wiener+indices+of+graphs.pdf

4 1 t h em a x i m u mr e v e r s ew i e n e ri n d e xo fu n i c y c l i cg r a p h sw i t h c y c l el e n g t h 4 2 t h em a x i m u mr e v e r s ew i e n e ri n d e xo fu n i c y c l i cg r a p h sw i t h n u m b e ro fp e n d e n tv e r t i c e s 4 3t h em a x i m u mr e v e r s ew i e n e ri n d e xo fu n i c y c l i cg r a p h sw i t h m a x i m u m d e g r e e r e f e r e n c e s a c k n o w l e d g e m e n t s 2 摘要 在点集为y ( g ) 的连通图g 中，w i e n e r 指数定义为 w ( g ) = d g ( u , v ) ， t ，t ，) y ( g ) 其中如( u ，u ) 是点u 和u 在图g 中的距离，而反w i e n e r 指数定义为 1 a ( g ) = 言佗( n 1 ) d 一( g ) ， 其中礼是图g 的点数，d 是图g 的直径。在给定匹配数的佗阶树中，给定匹配数的n 阶单 圈图中，给定悬挂点个数和圈长的n 阶单圈图中，我们分别得到了w i e n e r 指数的最小 值，而在给定圈长，给定悬挂点个数，给定最大度的礼阶单圈图中，我们分别得到了 反w i e n e r 指数的最大值。同时，我们也刻画出相应的极图。 关键词w i e n e r 指数；反w i e n e r 指数；树；单圈图；匹配数；悬挂点；圈长；最大度 3 a b s t r a c t f o rac o n n e c t e dg r a p hgw i t hv e r t e x - s e ty ( g ) ，t h ew i e n e ri n d e xo fgi sd e f i n e da s w ( g ) = d a ( u ，口) ， u ，v g v ( a ) w h e r ed a ( u ，u ) i st h ed i s t a n c eb e t w e e nv e r t i c e s 让a n dvi ng ，a n dt h er e v e r s ew i e n e r i n d e xo fgi sd e f i n e da s a ( g ) = 互1 佗( n 一1 ) d 一( g ) ， w h e r e 礼i st h en u m b e ro fv e r t i c e s ，di st h ed i a m e t e ro fg i nt h i sp a p e r ，w ed e t e r m i n e t h em i n i m u mw i e n e ri n d i c e so f 佗一v e r t e xt r e e sw i t hg i v e nm a t c h i n gn u m b e r n - v e r t e xu n i - c y c l i cg r a p h sw i t hg i v e nm a t c h i n gn u m b e r ，n u m b e ro fp e n d e n tv e r t i c e sa n dc y c l el e n g t h ， r e s p e c t i v e l y , t h em a x i m u mr e v e r s ew i e n e ri n d i c e so f 扎一v e r t e xu n i c y c l i cg r a p h sw i t hg i v e n c y c l el e n g t h ，n u m b e ro fp e n d e n tv e r t i c e s ，m a x i m u md e g r e e ，r e s p e c t i v e l y w ea l s oc h a r a c - t e r i z et h ec o r r e s p o n d i n ge x t r e m a lg r a p h s k e y w o r d sw i e n e ri n d e x ；r e v e r s ew i e n e ri n d e x ；t r e e s ；u n i c y c l i cg r a p h s ；m a t c h i n gd a m - b e r ；p e n d e n tv e r t e x ；c y c l el e n g t h ；m a x i m u md e g r e e 4 1i n t r o d u c t i o n 1 1d e f i n i t i o n sa n dt e r m i n o l o g i e s ag r a p hgi sa no r d e r e dt r i p l e ( y ( g ) ，e ( g ) ，妒g ) c o n s i s t i n go fan o n e m p t ys e tv ( g ) o f v e r t i c e s ，as e te ( g ) ，d i s j o i n tf r o my ( g ) ，o fe d g e s ，a n da ni n c i d e n c ef u n c t i o n 矽gt h a t a s s o c i a t e sw i t he a c he d g eo fga nu n o r d e r e dp a i ro f ( n o tn e c e s s a r i l yd i s t i n c t ) v e r t i c e so f g i fei sa ne d g ea n d 让a n dva r ev e r t i c e ss u c ht h a tc a ( e ) = 伽，t h e nei ss a i dt oj o i n 让 a n d ：t h ev e r t i c e sua n d 口a r ec a l l e dt h ee n d so fe t h ee n d so fa ne d g ea r es a i dt ob e i n c i d e n tw i t ht h ee d g e ，a n dv i c ev e r s a ag r a p hhi sas u b g r a p ho f g ( w r i t t e nh g ) i fv ( h ) y ( g ) ，e ( h ) e ( g ) ，a n d 矽日i st h er e s t r i c t i o no f 忆t oe ( 日) t w ov e r t i c e sw h i c ha r ei n c i d e n tw i t hac o m m o ne d g ea r ea d j a c e n t ，a sa r et w oe d g e s w h i c ha r ei n c i d e n tw i t hac o m m o nv e r t e x a ne d g ew i t hi d e n t i c a le n d si sc a l l e dal o o p a n da ne d g ew i t hd i s t i n c te n d sal i n k a g r a p hi ss i m p l ei fi th a sn ol o o p sa n dn ot w o o fi t sl i n k sj o i nt h es a m ep a i ro fv e r t i c e s t w ov e r t i c e sua n d o fga r es a i dt ob ec o n n e c t e di ft h e r ei sa ( u ，u ) 一p a t hi ng i f e v e r yp a i ro fv e r t i c e so fg a r ec o n n e c t e d ，t h e nga r ec a l l e dac o n n e c t e dg r a p h a nn - v e r t e xs i m p l ec o n n e c t e dg r a p hi sk n o w na sat r e eo rau n i c y c l i cg r a p hi f i t p o s s e s s e sn 一1o r 礼e d g e s i nt h i st h e s i s w ec o n c e n t r a t eo nt r e e sa n du n i c y c l i cg r a p h s l e tr a n d & b er e s p e c t i v e l yt h ep a t ha n dt h es t a ro nn 1v e r t i c e s l e t 繇b et h e c y c l eo nn 3v e r t i c e s i fua n dva r ec o n n e c t e di ng ，t h e nt h ed i s t a n c eb e t w e e nv e r t i c e sua n dvi ng ，d e n o t e d b yd g ( u ，u ) ，i st h el e n g t ho fas h o r t e s t ( “，u ) 一p a t hi ng t h e d i a m e t e ro fgi st h em a x i m u m d i s t a n c eb e t w e e nt w ov e r t i c e so fg f o ru y ( g ) ，l e td c ( u ) = 。y ( g ) d a ( u ，u ) a m a t c h i n gm o ft h eg r a p hgi sas u b s e to fe ( g ) s u c ht h a tn ot w oe d g e si nms h a r e ac o m m o nv e r t e x am a t c h i n gmo fgi ss a i dt ob em a x i m u m ，i ff o ra n yo t h e rm a t c h i n g m 7o fg ，l m 7 i l m i t h em a t c h i n gn u m b e ro fgi st h en u m b e ro fe d g e so fam a x i m u m m a t c h i n gi ng i fm i sam a t c h i n go fag r a p hga n dv e r t e xu v ( g 1i si n c i d e n tw i t h a ne d g eo fm ，t h e n 口i ss a i dt ob em s a t u r a t e d ，a n di fe v e r yv e r t e xo fgi sm s a t u r a t e d ， t h e nmi sap e r f e c tm a t c h i n g f o ru y ( g ) ，l e tg c ( u ) b et h en e i g h b o rs e to fui ng l e td g ( u ) = i g c ( u ) i ，i e ，t h e d e g r e eo fu i ng av e r t e xo fd e g r e eo n ei ss a i dt ob eap e n d e n tv e r t e x f o rag r a p hgw i t hv y ( g ) ，g ud e n o t e st h eg r a p hr e s u l t i n gf r o mgb yd e l e t i n g t h ev e r t e xu ( a n di t si n c i d e n te d g e s ) 5 f o ra ne d g eu vo ft h eg r a p hg ( t h ec o m p l e m e n to fg ，r e s p e c t i v e l y ) ，g u v ( g + u v ， r e s p e c t i v e l y ) d e n o t e st h eg r a p hr e s u l t i n gf r o mgb yd e l e t i n g ( a d d i n g ，r e s p e c t i v e l y ) t h e e d g eu v 1 2 g r a p ht h e o r ya n dt o p o l o g i c a li n d i c e s a si sw e l lk n o w n ，g r a p ht h e o r yi so r i g i n a t e df r o mt h ep a p e rw r i t t e nb ye u l e ro nt h e s e v e nb r i d g e so fk i i n i g s b e r g a f t e re u l e r sp a p e r ，g r a p ht h e o r yg r a d u a l l yg a i n e dg r o u n d t h r o u g has e r i e so fa t t e m p t st os o l v ep a r t i c u l a rp r a c t i c a lp r o b l e m s ，s u c ha sc h i n e s ep o s t m a np r o b l e m ，h a m i l t o n i a np a t ha n dc y c l ep r o b l e m s ，t h ef o u rc o l o rp r o b l e m ，e t c c u r r e n t l y , g r a p ht h e o r yi sp l a y i n ga ni n c r e a s i n g l yi m p o r t a n tr o l ei ns u c haw i d er a n g eo f o t h e rs u b j e c t sa sp h y s i c s ，c h e m i s t r y , g e n e t i c s h i s t o r i c a l l y ，g r a p ht h e o r yh a sac l o s er e l a t i o n s h i pw i t hc h e m i s t r y i nt h e o r e t i c a lc h e m - i s t r ya t o m i cc o n n e c t i v i t yb e l o n g st ob a s i cf a c t sa n d ，f o rt h i sr e a s o n ，g r a p ht h e o r e t i c a lc o n - s i d e r a t i o n sh a v ea l w a y sp l a y e da ni m p o r t a n tr o l ei nc h e m i s t r y , t h u sg r a p ht h e o r ym a k e s o m es i g n i f i c a n tc o n t r i b u t i o n st ot h es o l u t i o n so fs o m ec h e m i s t r yp r o b l e m s i nc h e m i s t r yg r a p ht h e o r y , w eu s u a l l yu s eag r a p ho rat r e et or e p r e s e n tam o l e c u l e g r a p h i fav e r t e xr e p r e s e n t sa na t o ma n da ne d g er e p r e s e n t sav a l e n c eb o n db e t w e e na p a i ro fa t o m s ，t h e nt h ed e r i v a t i v eg r a p hi sac o r r e s p o n d i n gg r a p hw i t ham o l e c u l e ，w h i c h i sc a l l e dam o l e c u l eg r a p h t h et o p o l o g i c a li n d i c e sa r en u m b e r sa s s o c i a t e dw i t hc h e m i c a ls t r u c t u r e sv i at h e i r h y d r o g e n - d e p l e t e dg r a p h s ，w h i c hh a v eb e e no f t e nu s e di nt h em o d e l i n go fs t r u c t u r e - p r o p e r t yr e l a t i o n s h i p s i ti so b v i o u st h a tt h ei s o m o r p h i cg r a p h sa r eo ft h es a m ev a l u e f o rag i v e nt o p o l o g i c a li n d e x ，t h u st o p o l o g i c a li n d i c e sa r er e f e r r e dt oa sg r a p hi n v a r i a n t s m o d e l i n go fs t r u c t u r e - p r o p e r t yr e l a t i o n s h i p su s i n gt o p o l o g i c a li n d i c e st or e p r e s e n tt h e s t r u c t u r e so fc h e m i c a li n t e r e s th a sr e c e i v e dc o n s i d e r a b l ea t t e n t i o n t o p o l o g i c a li n d i c e sa r ea b l et or e f l e c tav a r i e t yo fp r o s p e r i t i e so fam o l e c u l eg r a p h t h e a d v a n t a g eo ft o p o l o g i c a li n d i c e si si nt h a tt h e ym a yb eu s e dd i r e c t l ya ss i m p l en u m e r i c a l d e s c r i p t o r si nq u a n t i t a t i v es t r u c t u r e - p r o p e r t yr e l a t i o n s h i p s ( q s p r ) a n di nq u a n t i t a t i v e s t r u c t u r e - a c t i v i t yr e l a t i o n s h i p s ( q s a r ) ，t h r o u g hc o m p a r i s o no ft h ei n d i c e so fd i f f e r e n t g r a p h s ，w em a yo b t a i nt h e i rc o r r e s p o n d i n gc h e m i c a l ，p h y s i c a lo rb i o l o g i c a lp r o p e r t i e s ， w h i c hm a k ec o n t r i b u t i o nt ot h er e s e a r c ho fo t h e rs u b j e c t s u n t i ln o w ，t h e r ea r eh u n d r e d so ft o p o l o g i c a li n d i c e sh a v eb e e ns t u d i e d ，s u c ha sw i e n e r i n d e x ，r a n d i 6i n d e x ，h o s o y ai n d e x ，m e r r i f i e l d - s i m m o n si n d e x e s p e c i a l l y , w i e n e ri n d e x i sr e c o g n i z e da st h ef i r s tp r o p o s e dt o p o l o g i c a li n d e x e v e r yt o p o l o g i c a li n d e xh a si t s 6 u n i q u ec h a r a c t e r i s t i ca n da d v a n t a g e ，t h u se v e r yp a r t i c u l a rt o p o l o g i c a li n d e x i sa p p l i e dt o t h er e s e a r c ho fap a r t i c u l a rp r o b l e m 1 3w i e n e ri n d e xa n dr e v e r s ew i e n e ri n d e x i n1 9 4 7 ，w i e n e r 【1 】p r o p o s e dw i e n e ri n d e xf o ra c y c l i cm o l e c u l e s ( t r e e s ) t h ew i e n e r i n d e xo fat r e egi sd e f i n e da s ( g ) = 九( e ) 佗。( e ) ， e e e ( g ) w h e r en l ( e ) a n dn 2 ( e ) a r er e s p e c t i v e l yt h en u m b e r so fv e r t i c e so fgl y i n go nt h et w os i d e s o ft h ee d g ee a f t e rs e v e r a ld e c a d e s ，h o s o y ai n 19 7 1 2 g a v et h ed e f i n i t i o no fw i e n e r i n d e xf o rc o n n e c t e dg r a p h si nt e r m so fd i s t a n c e sb e t w e e ni t sv e r t i c e s ，a n dt h ew i e n e r i n d e xo fac o n n e c t e dg r a p hgi sd e f i n e da s w ( a ) d a ( u ， ) = 专d a ( u ) u ，v c _ v ( a )。u c v ( g ) i nm a t h e m a t i c a ll i t e r a t u r e sw i e n e ri n d e xs e e m st ob ef i r s ts t u d i e do n l yi n1 9 7 61 3 1 f o r al o n gt i m em a t h e m a t i c i a n sw e r eu n a w a r eo ft h e ( e a r l i e r ) w o r ko nw i e n e ri n d e xd o n ei n c h e m i s t r y ( c f t h eb o o k 4 ) t h en a m e sl i k ed i s t a n c eo fag r a p h 【3 】a n dt r a n s m i s s i o n 5 w e r ea l s ou s e dt od e n o t ew i e n e ri n d e x s i n c ew i e n e ri n d e xi st h ef i r s tp r o p o s e dt o p o l o g i c a li n d e x ，i ti sb o u n dt oa t t r a c tt h e a t t e n t i o no fs c i e n t i s t si nm a t h e m a t i c sa n dc h e m i s t r y u n t i ln o w ，c o n s i d e r a b l er e s u l t so f w i e n e ri n d e xw e r eo b t a i n e d ，w h i c hm a k ew i e n e ri n d e xt ob eo n eo ft h em o s tt h o r o u g h l y s t u d i e dm o l e c u l a r - g r a p h - b a s e ds t r u c t u r e - p r o p e r t y - a c t i v i t y i n 【3 】，i tw a ss h o w nt h a tt h e p a t ha n dt h es t a ra r er e s p e c t i v e l yt h eu n i q u et r e e sw i t hm a x i m u ma n dm i n i m u mw i e n e r i n d i c e s an e c e s s a r yc o n d i t i o nf o ram o l e c u l a rd e s c r i p t o rt ob ea l la c c e p t a b l em e a s u r e o fb r a n c h i n gi st h a tw i t h i nt h es e to fa l l 礼v e r t e xt r e e s i t sv a l u e ss h o u l db ee x t r e m a l f o rra n d 瓯，s e e ，e g 。，【4 s t h u sw i e n e ri n d e xc a nb eu s e da sab r a n c h i n gi n d e x g u t m a ne ta 1 【2 0 1g a v ear e l a t i o nr e l a t e dt ot h ew i e n e ri n d i c e so fu n i c y c l i cg r a p h sa n d s o m eo fi t ss u b g r a p h s w h i c hs e e m st ob et h ef i r s tr e s u l to nt h ew i e n e ri n d e xo fu n i c y c l i c g r a p h s t h e r ea r ea l s os o m er e s u l t so nw i e n e ri n d e xw i t hs o m er e s t r i c t i o n ，s e e ，e g ， 3 8 4 1 1 i np a r t i c u l a r ，f o rw i e n e ri n d e xo ft r e e s ，t h e r ea r ev a r i o u so t h e re x p r e s s i o n si nt e r m s o fs u c ho t h e rp a r a m e t e r sa sl a p l a c i a ne i g e n v a l u e s ，t h ed e g r e e so ft h ev e r t i c e s 6 t h e m a t h e m a t i c a lp r o p e r t i e sa n dt h eu s ei nt h es t r u c t u r e - p r o p e r t y - a c t i v i t ym o d e l i n gc a nb e 7 f o u n di n 【6 _ l o 】- h o w e v e r ，i t sd e g e n e r a c ya n dl o wd i s c r i m i n a t i n gp o w e rh a v er e s u l t e di n l a c ko fu n a m b i g u o u s n e s sa n du n i q u e n e s si ni t sp r o p e r t i e s 【1 1 】 w i t ht h ea i mt oo v e r c o m et h es h o r t c o m i n go fw i e n e ri n d e x an u m b e ro fm a t h e - m a t i c a lc h e m i s t sh a v ec o m eu pw i t ht h em o d i f i c a t i o n s ，e x t e n s i o n sa n dv a r i a n t so ft h i s i n d e x r a n d i 6e ta 1 1 2 1i n t r o d u c e dah o v e lw i e n e rm a t r i x ，f o ri t sp o t e n t i a lu t i l i z a t i o ni n s t r u c t u r e - p r o p e r t ys t u d i e s i v a n c i u ce ta 1 i n t r o d u c e dw i e n e ri n d e xe x t e n s i o nb yc o u n t i n ge v e n o d dg r a p hd i s t a n c e s b a l a b a ne ta 1 【1 3 】p r o p o s e dan o v e ls t r u c t u r e - d e s c r i p t o r ， t h er e v e r s ew i e n e ri n d e x l e tgb eac o n n e c t e dg r a p hw i t hnv e r t i c e s t h e nt h er e v e r s ew i e n e ri n d e xo fgi s d e f i n e da s 【1 3 1 a ( g ) = 言佗( 礼一1 ) d 一( g ) ， 二 w h e r edi st h ed i a m e t e ro fg i n 【1 3 ，g e n e r a lf o r m u l a ef o raw e r ep r e s e n t e df o rb e y - e r a lc l a s s e so fg r a p l l s ，i n c l u d i n gc o m p l e t eg r a p h ，s t a r ，p a t h ，c y c l ea n dl i n e a rp o l y a c e n e s ， r e l a t i o n s h i p sb e t w e e n 人a n do t h e rs t r u c t u r e - d e s c r i p t o r s ，e s p e c i a l l yw i e n e ri n d e x ，w e r e d i s c u s s e d ，a n dq s p ri n v e s t i g a t i o n sd e m o n s t r a t e dt h eu s e f u l n e s so ft h i si n d e x i v a n c i u c e to f 【1 4 】h a v es h o w nt h a tai sa b l et op r o d u c ef a i rq s p rm o d e l sf o rs t a n d a r dg i b b s e n e r g yo ff o r m a t i o na n dr e f r a c t i v ei n d e xf o rs m a l la l k a n e s z h a n ga n dz h o u 2 7 r e p o r t e d t h a tt h ep a t ha n dt h es t a ra r er e s p e c t i v e l yt h eu n i q u et r e e sw i t hm a x i m u ma n dm i n i m u m r e v e r s ew i e n e ri n d i c e s t h u st h er e v e r s ew i e n e ri n d e xc a nb eu s e da sab r a n c h i n gi n d e x c a ia n dz h o u 【2 8 】s h o w e dt h a tt h ep a t ha n dt h ec o m p l e t eg r a p ha r er e s p e c t i v e l yt h e u n i q u ec o n n e c t e dg r a p h sw i t hm a x i m u ma n dm i n i m u mr e v e r s ew i e n e ri n d i c e s o t h e r r e s u l t so nr e v e r s ew i e n e ri n d e xc a l lb ef o u n di n 【2 7 3 1 】 8 2t h ew i e n e ri n d i c e so ft r e e s i nt h es e c t i o n ，w ed e t e r m i n et h et r e e ( s ) w i t hm i n i m u mw i e n e ri n d e xw i t hg i v e nm a t c h i n g n u m b e r f o ri n t e g e r s 几a n dmw i t h1 m 【n 2 j ，l e tv ( n ，m ) b et h es e to ft r e e sw i t hn v e r t i c e sa n dm a t c h i n gn u m b e rm o b v i o u s l y , i fg t ( 佗，1 ) ，t h e ngi st h es t a r w e a s s u m et h a t2 m l n 2 j r e c a l lt h a td a n k e l m a n n 【4 1 】d e t e r m i n e dm a x i m u mw i e n e ri n d e xo fc o n n e c t e dg r a p h s w i t h 竹5v e r t i c e sa n dm a t c h i n gn u m b e rm 2 ，a n dc h a r a c t e r i z e dt h eu n i q u ee x t r e m a l g r a p h ，w h i c ht u r n e do u tt ob eat r e e t h u s ，t h em a x i m u mw i e n e ri n d e xo ft r e e si nt ( n ，m ) a n dt h eu n i q u ee x t r e m a lg r a p hh a v eb e e nk n o w n z h o ua n dt r i n a j s t i 6 4 2 】d e t e r m i n e d m i n i m u mw i e n e ri n d e xo fc o n n e c t e dg r a p h sw i t hn 5v e r t i c e sa n dm a t c h i n gn u m b e r m 2 ，a n dc h a r a c t e r i z e dt h ee x t r e m a lg r a p h s 2 1t h em i n i m u mw i e n e ri n d e xo ft r e e sw i t hg i v e nm a t c h i n g n u m b e r f i r s tw eg i v es o m el e m m a sw i l lb eu s e d t h ef o l l o w i n gl e m m ai se a s y l e m m a2 1 l e tg t ( 2 m ，m ) ，w h e r em 2 t h e ngh a sap e n d e n tv e r t e xw h o s e u n i q u en e i g h b o ri so fd e g r e et w o l e m m a2 2 4 7 ，4 3 】l e tg ( 佗，m ) ，w h e r e 礼 2 m t h e nt h e r ei sam a x i m u m m a t c h i n gm a n dap e n d e n tv e r t e x 乱o fgs u c ht h a tui sn o tm s a t u r a t e d f o ru y ( g ) ，l e tt h ee c c e n t r i c i t yo fu ，d e n o t e db ye c c ( u ) ，b et h em a x i m u md i s t a n c e f r o m 仳t oa l lo t h e rv e r t i c e si ng l e m m a2 3 l e tgb ea n 几- v e r t e xc o n n e c t e dg r a p hw i t hap e n d e n tv e r t e xu b e i n g a d j a c e n tt ov e r t e xv ，a n dl e twb ean e i g h b o ro f d i f f e r e n tf r o m ，w h e r e 记4 t h e n w ( c ) 一w ( a 一乱) 一如( u ) + 3 住一4 w i t he q u a l i t yi fa n do n l yi fe c c ( v ) = 2 m o r e o v e r ，i fd g ) = 2 ，t h e n w ( g ) 一w ( c u u ) - 2 d g ( 叫) + 7 n 1 5 w i t he q u a l i t yi fa n do n l yi fe c c ( w ) = 2 9 p r o o f n o t et h a td a (