（應(yīng)用數(shù)學(xué)專業(yè)論文）randic指標(biāo)與圖的若干不變量.pdf

摘要 摘要 在歷史上，圖論與化學(xué)有著非常緊密的聯(lián)系?；瘜W(xué)結(jié)構(gòu)可以很簡單地表示成 圖的形式，這樣的圖也稱為化學(xué)圖，或者分子圖。分子的拓?fù)渲笜?biāo)足從化學(xué)圖集 合到實數(shù)集合的一個映射，理論化學(xué)家和數(shù)學(xué)家提出了眾多的拓?fù)渲笜?biāo)并進(jìn)行研 究本文主要研究一種廣受化學(xué)家和數(shù)學(xué)家關(guān)注的拓?fù)渲笜?biāo)一一r a n d i 6 指標(biāo)， 研究r a n d i 6 指標(biāo)與圖的其它若干不變量之間的關(guān)系，如色數(shù)，半徑，直徑，最小 度，最大度，階數(shù)和邊數(shù)，等等 1 9 7 5 年著名理論化學(xué)家、數(shù)學(xué)化學(xué)家p 沮n d i 6 提出了連通性指標(biāo)，即r a n d i 6 指標(biāo)。( 化學(xué)) 圖g 的p 沮n d i 6 指標(biāo)定義為r ( a ) = 。惦e f g l ( d ( 讓) d ( 穢) ) 一 ，其中 d ( 玨) 表示圖g 中頂點u 的度數(shù)。l h n d i 6 指標(biāo)與分子的物理化學(xué)性質(zhì)，如沸點、 表面積等，都有著緊密的聯(lián)系。1 9 9 8 年，著名數(shù)學(xué)家b o l l o b l s 和e r d s s 將r ( g ) 中的一萬1 替換為任意的實數(shù)o t ，從而提出了廣義r a n d i 6 指標(biāo)的定義。理論化學(xué) 家和數(shù)學(xué)家對廣義r a n d i 6 指標(biāo)進(jìn)行研究，并且得到了很多重要而深刻的結(jié)果。 第一章足引言部分，介紹了p 諗n d i 6 指標(biāo)的定義、研究背景，以及本文中涉及 到的相關(guān)概念和基本知識。以下五章為本文的主要貢獻(xiàn)： 在第二章中，我們指出了h a n s e n 和m 6 1 0 t 的文章 v a r i a b l en e i g h b o r h o o d s e a r c hf o re x t r e m a lg r a p h s6 ：a n a l y z i n gb o u n d sf o rt h ec o n n e c t i v i t yi n d e x j c h e m i n f c o m p u t s c i 4 3 ( 2 0 0 3 ) ，1 - 1 4 中兩個定理證明的錯誤，并給出了正 確的證明這兩個定理刻畫了化學(xué)樹的r a n d i 6 指標(biāo)和葉子點數(shù)之間的聯(lián)系 在第三章中，我們討論了圖g 的r a n d i 6 指標(biāo)r ( c ) 和最小度6 ( g ) 之間的關(guān) 系，并部分解決了b o l l o b 缸和e r d s s 提出的公開問題。1 9 8 8 年，s h e a r e r 證明了 如果圖的最小度6 ( g ) 1 ，那么r ( g ) 、，傷2 ，幾個月后a l o n 將這個界改進(jìn)到 而一8 1 9 9 8 年，b o u o b 缸和e r d 5 s 證明，如果5 ( a ) 1 ，則有r ( g ) 而一1 ， 其中等號成立當(dāng)且僅當(dāng)g 是星圖。b o l l o b a s 和e r d s s 提出如下問題：給定圖 g 的最小度6 ( g ) ，r ( g ) 的最小值是多少? 在2 0 0 2 年，d e l o r m e ，f a v a r o n 和 i 摘要 r a u t e n b a c h 針對這一問題提出了如下猜想：如果圖g 的最小度6 ( g ) k ，那么 r ( g ) 糕+ ( ：) 矗，其中等號成立當(dāng)且僅當(dāng)圖g 是由完全二部圖紙，佗一七 做如下變換得到：在玩m 一知含有k 個頂點的那部分內(nèi)的任意兩個頂點連一條邊 提出猜想后，他們證明了k = 2 時猜想是成立的。我們驗證了k = 3 時猜想的 正確性，由此很容易地得到猜想中的不等式對所有的化學(xué)圖也是成立的。更進(jìn)一 步，我們證明了當(dāng)忌4 時，如果圖的頂點數(shù)滿足竹；而3 ，則猜想是成立的。 在第四章的第一部分，我們完全解決了c a p o r o s s i 和h a n s e n 提出的關(guān)于圖 的r a n d i d 指標(biāo)和色數(shù)的猜想：對頂點數(shù)n 2 的連通圖g ，r ( g ) 趔2 + 了霜1( 4 x ( a ) 一1 + 禮一x ( a ) ) ，而且對所有的禮以及2 x ( a ) 竹，這個界是 緊的，其中圖g 的色數(shù)x ( a ) 是指使得圖g 有正常頂點著色( 相鄰頂點所著顏 色不同) 的最小顏色數(shù)目在第二部分中我們考慮了f a j t l o w i c z 提出的關(guān)于圖的 r a n d i d 指標(biāo)和半徑的猜想：對任意連通圖g ，r ( a ) r ( a ) 一1 ，其中圖g 的半徑 r ( g ) = m _ i n 移gm a y 。u ( g ) d ( u ，v ) 。根據(jù)e r d 5 s 等人的關(guān)于圖的半徑和最小度的結(jié) 果，我們證明了若g 是具有竹個頂點，最小度為j ( g ) 的連通圖，如果6 ( g ) 詈 且禮2 5 ，則猜想成立；更進(jìn)一步，對任意實數(shù)0 以a n d d 7 d e n o t e st h a tt h en u m b e ro fv e r t i c e sw i t hd e g r e ed ii sq t t h el e n g t ho fap a t hi st h en u m b e ro fe d g e si nt h ep a t h t h ed i s t a n c ed ( t ，u ) b e t w e e nt w ov e r t i c e sua n d i st h el e n g t ho fas h o r t e s tp a t hb e t w e e n 釓a n d i fgh a sn os u c hp a t hb e t w e e nv e r t i c e s 亂a n d ，t h e nd ( u ，秒) = o o ag r a p h gi sc o n n e c t e di ft h e r ee x i s t sap a t hb e t w e e ne v e r yp a i ro fv e r t i c e si ng t h e d i a m e t e rd ( g ) o fgi st h em 腳m u md i s t a n c eb e t w e e na n yp a i ro fv e r t i c e so f g ，i e ，d ( c ) = m a x u , v e v ( o ) d ( u ，u ) t h ee c c e n t r i c i t yo fav e r t e x ，w r i t t e ne ( 亂) ， i sm a vd ( u ， ) n o t et h a tt h ed i a m e t e re q u a l st h em a x i m u mo ft h ev e r t e x e c c e n t r i c i t i e s t h er a d i u so fag r a p hg i sr ( v ) = m i n u y e ( 亂) f o rag i v e ng r a p h g ，av e r t e xc o l o r i n go fg i sc a l l e dp r o p e ri fa n yt w oa d ja c e n tv e r t i c e sa r ea s s i g n e d d i f f e r e n tc o l o r s t h ec h r o m a t i cn u m b e rx ( a ) o fgi st h em i n i m u mn u m b e ro f c o l o r st h a ta x en e e d e dt oc o l o rg p r o p e r l y 1 3o v e r v i e wo ft h et h e s i s f o ra ( c h e m i c a l ) g r a p hg = ( k e ) ，t h eg e n e r a lr a n d i di n d e x 吼( g ) o fg i s d e f i n e da st h es u mo f ( d ( 亂) d ( 口) ) no v e ra l le d g e s 釷 o fg ，w h e r ed ( u ) d e n o t e st h e d e g r e eo fav e r t e xu o fg ，i e ， r a ( g ) = ( d ( 讓) d ( 鈔) ) 口 w h e r eo i sa l la r b i t r a r yr e a ln u m b e r 。 u v e e 5 c h a p t e r1 i n t r o d u c t i o na n dh i s t o r i c a ln o t e s i n1 9 7 5 ，t h ec h e m i s tr a n d i 6 【s g p r o p o s e dat o p o l o g i c a li n d e xr ( r 一1a n d r 一 ) u n d e rt h e n a m e “t h eb r a n c h i n gi n d e x ”，w h i c hi sn o wa l s oc a l l e d “t h er a n d i d i n d e z o r “t h ec o n n e c t i v i t yi n d e z s u i t a b l ef o rm e a s u r i n gt h ee x t e n to fb r a n c h i n g o ft h ec a r b o n - a t o ms k e l e t o no fs a t u r a t e dh y d r o c a r b o n s l a t e r ，i n1 9 9 8b o h o b f i s a n de r d s s 1 4 g e n e r a l i z e dt h i si n d e xb yr e p l a c i n g 一 w i t ha n yr e a ln u m b e ra ， w h i c hi sc a l l e dt h eg e n e r a lr a n d i 6 , i n d e x t h ez e r o t h o r d e rr a n d i di n d e x , c o n c e i v e db yk i e ra n d h a l l 5 7 ，5 9 ，i sd e f i n e d a s ， 。r ( g ) = o r 一- 2 ( g ) = d ( 釓) 一i 1 t g w h e r et h es u m m a t i o ng o e so v e ra l lv e r t i c e so fg i na n a l o g yt ot h er a n d i di n d e x ， l ia n dz h e n g 【7 4 d e f i n e dt h ez e r o t h o r d e rg e n e r a lr a n d i di n d e xo 耽( g ) o fa g r a p hg ， o 風(fēng)( g ) = d ( u ) 。， t 上g w h e r eo li sa na r b i t r a r yr e a ln u m b e r a l r e a d yr a n d i 6n o t i c e dt h a tt h e r ei sag o o dc o r r e l a t i o nb e t w e e nt h er a n d i 6 i n d e xra n ds e v e r a lp h y 7 s i c o c h e m i c a lp r o p e r t i e so fa l k a n e s ：b o i l i n gp o i n t s ，c h r o - m a t o g r a p h i cr e t e n t i o nt i m e s ，e n t h a l p i e so ff o r m a t i o n ，p a r a m e t e r si nt h ea n t o i n e e q u a t i o nf o rv a p o rp r e s s u r e ，s u r f a c ea r e a s ，e t c i ns u b s e q u e n ty e a r sc o u n t l e s s a p p l i c a t i o n so fr w e r er e p o r t e d ，m o s to ft h e mc o n c e r n e dw i t hm e d i c i n a la n d p h a r m a c o l o g i c a li s s u e s at u r n i n gp o i n ti nt h em a t h e m a t i c a le x a m i n a t i o no ft h e r a n d i da n dg e n e r a lr a n d i 6i n d e xh a p p e n e di nt h es e c o n dh a l fo ft h e1 9 9 0 s ，w h e n as i g n i f i c a n ta n de v e rg r o w i n gr e s e a r c ho nt h i sm a t t e rs t a r t e d ，r e s u l t i n gi nn u m e r - o u sp u b l i c a t i o n s a st h ec h e m i s tg u t m a ni n 【4 6 m e n t i o n e dt h a t ：“i nc h e m i c a l g r a p ht h e o r y , t h ec o n n e c t i v i t yi n d e xa c h i e v e dar a p i da n de n o r m o u ss u c c e s s i t s o o nb e c a m et h em o s tp o p u l a ra n dm o s tf r e q u e n t l ye m p l o y e ds t r u c t u r ed e s c r i p - t o r ，u s e di ni n n u m e r a b l eq s p ra n dq s a rs t u d i e s i tw a ss o o ng e n e r a l i z e d ( t o h i g h e r - o r d e re o n n e c t i 、，i 鑼i n d i c e s ) a n dp a r a m e t r i z e d ( s oa st ob ea p p l i c a b l et o h e t e r o a t o m - c o n t a i n i n gs p e c i e s ) r e c e n t l y , t h er a n d i di n d e xw a ss t u d i e db yb o t hm a t h e m a t i c i a n sa n dt h e o r e t - i c a lc h e m i s t s ，w h oe s t a b l i s h e daf e wo fi t sf u n d a m e n t a lm a t h e m a t i c a lp r o p e r t i e s f o ras u r v e yo fr e s u l t s ，w er e f e rt ot h eb o o k 【6 2 w r i t t e nb yl ia n dg u t m a na n d 6 t h es u r v e y 【6 7 】 n o t et h a tt h er a n d i di n d e xa n dt h ez e r o t h - o r d e rr a n d i 6i n d e xa r eb o t h g r a p hi n v a r i a n t s g r a p ht h e o r yc o n t a i n sal a r g en u m b e ro fr e l a t i o n sb e t w e e n g r a p hi n v a r i a n t s s o m eo ft h e m 齜ee q u a l i t i e s ，m o s to ft h e ma r ei n e q u a l i t i e s ， o f t e nn o n l i n e a ri no i l eo rm o r ep a z a m e t e r s t h er e l a t i o n sb e t w e e nt h er a n d i 6 i n d e xa n ds o m eo t h e rg r a p hi n v a r i a n t sa r el i s t e da 8f o l l o w s 1 3 1r a n d i di n d e xa n dt h en u m b e ro fp e n d e n tv e r t i c e so f c h e m i c a lt r e e s ac h e m i c a lg r l p h ( t r e e ) i sag r a p h ( t r e e ) i nw h i c ht h em a x i m u md e g r e ei s 1 1 0m o r et h a n4 l e ttb eac h e m i c a lt r e eo fo r d e r 佗麗t hn lp e n d e n tv e r t i c e s t h e r ea r em a n yr e s u l t so i lt h er e l a t i o nb e t w e e nt h er m a d i 6i n d e xr ( t ) a n dn l ， o n ec a ns e e 【6 9 ，7 3 ，9 7 ，9 9 i nf a c t ，i n2 0 0 3 ，h a , n s e na n dm 6 l o t 【5 2 s t u d i e dt h er e l a t i o no fr ( t ) a n d t h en u m b e ro fp e n d e n tv e r t i c e s i n 5 2 】，t h ea u t h o r si n t r o d u c e dt w oc l a s s e so f c h e m i c a lt r e e sl e ( 禮，n 1 ) a n du ( 釓，死1 ) ( s e ec h a p t e r2 ) t w ot h e o r e m sa r es t a t e d a sf o l l o w s ： t h e o r e m1 3 1 ( h a n s e na n dm 6 1 0 t ，【5 2 ) l e ttb e 口c h e m i c a lt r e eo lo r d e r 禮w i t h 釓1 5p e n d e n tv e r t i c e s t h e n 即，蘭+ ( 擊一1 ) + 蘭一以， 3 塒統(tǒng)e q u a l i t y 諺a n dd n 冶諺n 1 話刪帆a n dt t si s o m o r p m ct ol e ，n 1 ) t h e o r e m1 3 2 ( h a n s e na n dm 6 l o t ， 5 2 】) 二e ttb eac h e m i c a lt r e eo fo r d e r 佗w i t h 仡1 3p e n d e n tv e r t i c e s t h e n r ( t ) 警一面n - ， w h e r ea o = 一擊一赤0 0 5 1 3 ，w i t he g 讓。屁匆i f8 n do n l y 礦ti si s o m o r p h i ct o v ( n ，n 1 ) h o w e v e r ，w ef m m ds o m em i s t a k e si nt h e i rp r o o f s i nc h a p t e r2 ，w ew i l lg i v e t h ec o r r e c t e dp r o o f s 7 c h a p t e r1 i n t r o d u c t i o na n dh i s t o r i c a ln o t e s 1 3 2r a n d i di n d e xa n dt h em i n i m u md e g r e e i n1 9 8 8 ，s h e a r e rp r o v e dr ( g ) 瓶2i f 占( g ) 1 af e wm o n t h sl a t e ra l o n i m p r o v e dt h i sb o u n dt o 何一8 b o l l o b 缸a n de r d s s 1 4 】p r o v e dt h a ta m o n ga l l g r 印h so fo r d e r 佗w i t h6 ( g ) 1 ，t h es t a r a t t a i n st h em i n i m u mp 沮n d i di n d e x 扔再1 b o l l o b 五sa n de r d s sa s k e df o rt h em i n i m u mv a l u eo ft h er a n d i di n d e x f o rg r a p h sw i t hg i v e nm i n i m u md e g r e e d e l o r m e ，f a v a r o na n dr a u t e n b a c h 3 2 g a v ea na n s w e ro fk = 2a n dp r o p o s e dt h ef o l l o w i n gc o n j e c t u r e c o n j e c t u r e1 3 3 ( d e l o r m e ，f a v a r o na n dr a u t e n b a c h ，【3 2 ) l e tg = ( ve ) b eag r a p ho lo r d e rnw i t h6 ( g ) k t h e n 即，蔫苦+ ( 耋) w i t he q u a l i t y 礦a n do n l yi lg = 雄，n 卻w h e r e 磁艫南i sag r a p ho b t a i n e d 加ma c o m p l e t eb i p a r t i t eg r a p hj 屯m 一鳧b yj o i n i n ge a c hp a i ro lv e r t i c e si nt h ep a r tw i t hk v e r t i c e sb yan e we d g e i n 【3 a o u c h i c h ea n dh a n s e nf o u n de x a m p l e ss h o w i n gt h a tt h ec o n j e c t u r ei s n o tt r u e ，a n dg a v eam o d i f i e df o r m i nc h a p t e r3 ，w ew i l lc o n s i d e rc o n j e c t u r e 1 3 3 w ev e r i f yt h i sc o n j e c t u r ef o rk = 3 ，w h i c hc a ne a s i l yl e a dt ot h ec o n c l u s i o n t h a tt h ei n e q u a l i t yo ft h ec o n j e c t u r eh o l d sf o ra l lc h e m i c a lg r a p h s f u r t h e r m o r e ， w ep r o v et h a tf o rk 4 ，t h ec o n j e c t u r ei st r u ef o ra n yg r a p ho fo r d e r 竹3 k 3 1 3 3r a n d i di n d e xa n dt h ec h r o m a t i cn u m b e r ，t h er a d i u s c a p o r o s s ia n dh a n s e n 【2l 】p r o p o s e dt h ef o l l o w i n gc o n j e c t u r eo nt h er e l a t i o n b e t w e e nr a n d i di n d e xa n dt h ec h r o m a t i cn u m b e r ，w h i c hi sa l s or e f e r r e di n 【6 2 i nt h ef i r s tp a r to fc h a p t e r4 ，w ew i l lg i v eap o s i t i v ep r o o ft oc o n j e c t u r e1 3 4 c o n j e c t u r e1 3 4 ( c a p o r o s s ia n dh a n s e n ，【2 1 ) f o ra n yc o n n e c t e dg r a p hg o fo r d e rn 2w i t hc h r o m a t i cn u m b e rx ( a ) a n dr a n d i di n d e x 冗( g ) ， r ( c ) t x ( a ) - 2 + 志1 2 。、元一 ( x x ( c ) - 1 + n - x ( c ) ) m o r e o v e r , t h eb o u n di ss h a r pf o ra l l 禮a n d2 x ( a ) n 8 c h a p t e r1 i n t r o d u c t i o na n dh i s t o r i c a ln o t e s i n 3 8 】，f a j t l o w i c zp r o p o s e dt h ef o l l o w i n gc o n j e c t u r eo nt h er e l a t i o nb e t w e e n t h er a n d i di n d e xa n dt h er a d i u s ，w h i c hi sa l s or e f e r r e di n 6 2 c o n j e c t u r e1 3 5 ( f a j t l o w i c z ， 3 s ) f o ra n yc o n n e c t e dg r a p hg ， r ( g ) r ( a ) 一1 ， w h e r er ( g ) d e n o t e st h er a d i u s 吖g c a p o r o s s ia n dh a n s e n 2 1 】p r o v e dt h a tf o ra l lt r e e st ，r ( t ) r ( t ) + 以一2 ， a n df o rt r e e ste x c e p te v e np a t h s ，r ( t ) r ) i n 7 6 ，t h ec o n j e c t u r ei sv e r i f i e d f o ru n i c y c l i cg r a p h s ，b i c y c l i cg r a p h sa n dc o n n e c t e dg r a p h so fo r d e rn 9w i t h 6 ( g ) 22 r e c e n t l y , y o ua n dl i u 9 8 】p r o v e dt h a tt h ec o n j e c t u r ei st r u ef o r b i r e g u l a rg r a p h s ，t r i c y c l i cg r a p h sa n dc o n n e c t e dg r a p h so fo r d e rn 1 0 i nt h es e c o n dp a r to fc h a p t e r4 ，w ew i l lp r o v et h a tf o ra n yc o n n e c t e dg r a p h go fo r d e rnw i t hm i n i m u md e g r e e6 ( g ) ，t h ec o n j e c t u r eh o l d sf o r6 ( g ) 詈a n d 禮22 5 ，f u r t h e r m o r e ，f o ra n ya r b i t r a r yr e a ln u m b e r0 l ，i f6 ( g ) g n ， c o n j e c t u r e1 3 5h o l d sf o rs u f f i c i e n t l yl a r g e 禮 1 3 4t h ez e r o t h - o r d e r ( g e n e r a l ) r a n d i di n d e x i ts h o u l db en o t e dt h a tt h ez e r o t h - o r d e rg e n e r a lr a n d i 6i n d e xi ss o m e t i m e s r e f e r r e dt oa s “t h eg e n e r a lf i r s tz a g r e bi n d e x 8 1 ，1 0 1 ，i nv i e wo ft h ef a c tt h a t ( d ( “) ) 2i ss o m e t i m e sc a l l e d “t h ef i r s tz a g r e bi n d e x f o r 口= - 1 ，i ti sa l s o t c a l l e d t h ei n v e r s ed e g r e e ，s o m e t i m e sd e n o t e db y “，( g ) ”( s e e 【3 6 ，3 8 ，7 9 】) i nf a c t ，t h e r ea r em a n yr e s e a r c h e so nt h i si n d e x ，w h i c hh a sm a n yu s e f u la p p l i - c a t i o n si ni n f o r m a t i o nt h e o r ya n dn e t w o r kr e h a b i h t y , a n dr e c e i v e dc o n s i d e r a b l e a t t e n t i o n sa l s oi ng r a p ht h e o r y ( s e e 【1 ，1 1 ，1 2 ，2 6 ，3 1 ，8 0 ，8 8 】) p a v l o v i d 8 3 】d e t e r m i n e dt h es h a r pu p p e rb o u n do ft h ez e r o t h - o r d e rr a n d i d i n d e xo 凰o f ( n ，m ) - g r a p h s i n 7 2 】l ia n dz h a og a v et h es h a r pu p p e ra n dl o w e r b o u n d so fo 吼o ft r e e s ，w i t ht h ee x p o n e n tqe q u a lt om ，一m ，鬲1a n d 一磊1 ，w h e r e m22i sa ni n t e g e r l a t e r ，l ia n dz h e n g 【7 4 g a v ea na l t e r n a t i v ep r o o ff o r g e n e r a lr e a ln u m b e rq z h a n ga n dz h a n g 【1 0 1 】d e t e r m i n e dt h es h a r pu p p e rm a d 9 l o w e rb o u n d so fo r qo fu n i c y c h cg r a p h s ，w h i l ez h a n g ，w a n ga n dc h e n g 【1 0 0 d e t e r m i n e dt h es h a r pu p p e ra n dl o w e rb o u n d so fb i c y c l i cg r a p h s i n 【5 5 ，6 6 ，t h e a u t h o r sc o n s i d e r e dt h ee x t r e m a lv a l u e so fo 吼f o rt h ec o n n e c t e d ( n ，m ) 一g r a p h s a n dt h e yg a v et h es h a r pl o w e rb o u n do fo 凰f o r 口 1 ，a n dt h es h a r p u p p e rb o u n do fo 吼f o r 口 1 t h e r ea r ea l s os o m eg a p s f o rc h e m i c a lt r e e s ，l ia n dz h a o 【7 2 d e t e r m i n e dt h es h a r pa n dl o w e rb o u n d s o fo 吼f 缸a n ya i nc h a p t e r5 ，w ew i l li n v e s t i g a t et h ez e r o t h o r d e rg e n e r a l r a n d i 6i n d e xf o rc h e m i c a l ( 竹，m ) 一g r a p h s ，i e ，c o n n e c t e ds i m p l eg r a p h sw i t h 佗 v e r t i c e s me d g e sa n dm a x i m u md e g r e ea ，tm o s t4 w ew i l lg i v et h es h a r pu p p e r a n dl o w e rb o u n d so fo r af o ra n y 口 1 3 5t h ei n v e r s ed e g r e ea n dt h ed i a m e t e r w ed e n o t et h ei n v e r s ed e g r e eo r l ( a ) b yj ( g ) t h e r ei sag r a f f i t ic o n j e c t u r e u ( a ) i ( a ) ( s e e 【3 8 ，4 1 ) ，w h e r eu ( a ) i st h ea v e r a g ed i s t a n c eo fg h o w e v e r ， t h ec o n j e c t u r ew a sr e f u t e db ye r d s s ，p a c ha n ds p e n c e ri n 【3 6 t h e yp r o v e dt h a t ， i fgi sac o n n e c t e dg r a p ho fo r d e r 禮a n di ( g ) 3 ，t h e n ( 蘭吶( 1 ) ) 器糾v ) 叫v ) a n dd ( n ，r ) = m a x d ( g ) ： d a n k e l m a n ne ta 1 【3 0 i m p r o v e dt h eu p p e rb o u n db yaf a c t o ro f2 ， ，( g ) r ) d ( g ) ( 3 ，( g ) + 2 + 。( 1 ) ) 面l o 面g n ， w h i c hi sa l s oa l lu p p e rb o u n do nt h ea v e r a g ed i s t a n c es i n c ep ( g ) d ( g ) i nc h a p t e r6 ，w ew i l lg i v et h es h a r pu p p e rb o u n d sf o rt r e e sa n du n i c y c f i c g r a p h s ，w h i c hi m p r o v et h ea b o v eu p p e rb o u n db y af a c t o ro fa p p r o x i m a t e l y 4 軍墜w es h o wt h a tf o ra t r e et o f o r d e r 釓 5l o g l o g n d ( t ) 3 n - 2 1 ( t ) + 1 - v 4 1 ( t ) 2 _ - 廣( 4 n - 4 ) i ( t ) + n 2 - 2 一n - 7 ， w h i l ef o rau n i c y c f i cg r a p hgo fo r d e r 釓 d ( g ) 3 n - 2 i ( g ) - 1 - v 4 i ( g ) 2 - 丁( 4 n - 1 2 ) i ( g ) + n 2 - 6 一n + 1 1 0 c h a p t e r2 r a n d i 6i n d e xa n dt h en u m b e ro f p e n d e n t 瞻r t i c e so fc h e m i c a lt r e e s i nt h i sc h a p t e r ，w ep o i n to u tt h em i s t a k e si nt h ep r o o f so ft w ot h e o r e m si n t h ep a p e ro fh a n s e na n dm 6 1 0 t ，i nw h i c ht h e ys t u d i e dt h er e l a t i o no ft h er a n d i 6 i n d e xa n dt h en u m b e ro fp e n d e n tv e r t i c e so fc h e m i c a lt r e e s w ep r e s e n tt h e c o r r e c t e dp r o o f s 2 1b o u n d so fh a n s e na n dm 6 l o t t h er a n d i di n d e xn ( o ) o fag r a p hg ，a l s oc a l l e dt h ec o n n e c t i 、，i t yi n d e x ，w a s i n t r o d u c e db yt h ec h e m i s tr a n d i 6u n d e rt h en a n q e “t h eb r a n c h i n gi n d e x ”i n1 9 7 5 a st h es u i no f1 、d ( u ) d ( v ) o v e ra l le d g e s 讓口o fg ，w h e r ed ( u ) d e n o t e st h ed e g r e e o fav e r t e xui ng ，i e ， 即) = ，薹麗麗1 ev t ”，”。， av e r t e xo fd e g r e e1i sc a l l e dat e a v e r t e x ( o rs i m p