（应用数学专业论文）准树图的最大广义randic指标.pdf

准树图的最大广义r a n d i 6 指标 摘要 为了研究饱和碳氢化合物的碳原子骨架的分支程度，著名化学家r a n d i 6 于 1 9 7 5 年提出了种重要的分子拓扑指标一分支指标：r = 删e ( d ( 钍) d ( 钉) ) 一i 1 ， 其中d ( u ) 表示顶点u 的度分支指标又称为连通指标或者r a n d i 6 指标，它与 分子的许多物理化学性质有着密切的关系之后，在1 9 9 8 年b o l l o b l s ，e r d 6 s 和 a m i 6 等分别独立地提出了广义r a n d i 6 指标，定义为m ( g ) = u t i e ( d ( t ) d ( ) ) a ， 其中。为任意的实数对于广义r a n d i 6 指标的研究目前主要是确定给定图类中 的极图，即具有最大或最小的广义r a n d i 6 指标的图个图称为准树图，如果 l 存在个点札y ( g ) ，使图g 一钆是棵树本文中，我们分别完全刻画了在 口21 和o l - 2 1 时，具有最大广义r a n d i 6 指标的准树图( 不包括树) 的图 类，并且对于0 o t 1 和一2 1 0 0 ，我们给出了相应极图的若干性质 关键词准树图，最大的广义r a n d i 6 指标 准树图的最大广义r a n d i 6 指标 a b s t r a c t i ns t u d y i n gt h ee x t e n to fb r a n c h i n go 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 ，r a n d i di n1 9 7 5p r o p o s e da ni m p o r t a n tt o p o l o g i c a li n - d e x b r a n c h i n gi n d e x ：r = 删炬e ( d ( 札) d ( u ) ) 一 ，w h e r ed ( t 正) d e n o t e st h e d e g r e eo fav e r t e xu b r a n c h i n gi n d e xi sa l s oc a l l e dt h ec o n n e c t i 们t yi n d e xo r r a n d i di n d e x t h er a n d i di n d e xi sc l o s e l yc o r r e l a t e dw i t hav a r i e t yo fp h y s i c o - c h e m i c a lp r o p e r t i e so fm o l e c u l a r l a t e ri n1 9 9 8 ，b o l l o b 缸，e r d d sa n da m i d e ta 1 i n d e p e n d e n t l yg e n e r a l i z e dt h i si n d e xt ob et h eg e n e r a lr a n d i di n d e x ： ( g ) = e v e e ( d ( u ) d ( v ) ) 口，w h e r eq i sa na r b i t r a r yr e a ln u m b e r t h eg e n e r a l r a n d i di n d e xh a sa t t r a c t e dt h ew i d ea t t e n t i o no fb o t ht h e o r e t i c a lc h e m i s t sa n d m a t h e m a t i c i a n s u pt on o w ，r e s e a r c hi n t e r e s to ng e n e r a lr a n d i di n d e xf o c u s m a i n l yo nt h ep r o b l e mo fd e t e r m i n i n gt h ee x t r e m a lg r a p l l si nag i v e nc l a s so f g r a p h s ag r a p hg i sc a l l e daq u a s i t r e eg r a p h ，i ft h e r ee x i s t s 札v ( a ) s u c h t h a tg 一仳i sat r e e i nt h i sp a p e r ，f o r “la n dq - 2 1 ，t h em a x i m u m v a l u eo ft h eg e n e r a lr a n d i di n d e xa n dt h ec o r r e s p o n d i n ge x t r e m a lq u a s i t r e e p r a p h s ( o t h e rt h a nt r e e s ) a r ed e t e r m i n e d f o r0 q 1a n d - 2 1 0 时，在q t ( n ) 中有最大的广义r a n d i d 指标的准树图一 定会有d o = 礼一1 准树图的最大广义r a n d i 芒指标 5 证明根据广义r a n d i 6 指标的定义不难看出，每条边的权都是个正数， 而且当参数值a 0 时，边u v 的权将会随着点u 或者点v 度的增加大而增大 设g q t ( n ) 并且满足d o 礼一2 g ，是由图g 通过添加与点u o 相关联 的边直到使点咖的度达到礼一1 而得到的图那么我们有g ，q t ( n ) ，而且 鼠( g ，) 玩：( g ) 。因此当o l 0 时，有最大的广义r a n d i 6 指标的准树图一定 会有d o = 礼一1 口 2 2a 1 定义2 2 1 设岛是个星，准树图砩是由星图& 通过添加条连接两 个悬挂点的边而得到的图( 见图1 ) 定义2 2 2 设岛是个星，准树图鄙_ 2 是由星图& 通过分别连接个 固定的悬挂点与剩下的其它n 一2 个悬挂点而得到的图( 见图1 ) 图1 t 、 、 1 j 、 0 一一 引理2 2 1 设图g q t ( n ) 且d o = 佗一1 ，如果树g u o 既不是星又不 准树图的最大广义r a n d i 5 指标 6 是双星，那么当口1 时。存在个新图g ，q t ( n ) ，使g ，一u o 是一双星并 且有心( g ) 吼( g ) 证明因为d o = 扎一1 ，g u o 既不是星图又不是双星，从而在g 一伽中 的一定存在三个点v l ，v 2 ，v 3 使v l v 2 ，v 2 v 3 e ( g ) ，且设d ( v 1 ) = p ，d ( v 2 ) = z ， d ( v 3 ) = q ，我们有p ，z ，q 3 假设g 中n ( v 1 ) 忱) = u o ，u l ，吻一2 ) ，n ( v 3 ) u 2 ) = u o ，w l ， w g 一2 ) ，令d = g v 3 w l - - - v 3 w g 一2 + v l w z + + v l w 口一2 ，那么g j q t ( n ) ( 见图2 ) 根据定义，我们有 q - - 2 r ( g 7 ) 一凡( g ) = ( o + 口一2 ) a 9 0 ) 矿( 叫七) + ( ( p + q 一2 ) 。一矿) k = l p - 2 芝二扩( u 七) + ( + q 一2 ) n p a ) l + ( 2 。一q a ) l q k = 1 + ( 2 。一q 。) ( 他一1 ) a + ( + q 一2 ) 。一p o ) ( n 一1 ) n ( ( p + q 一2 ) 口一p o ) f 。+ ( 2 。一矿) z a + ( 2 口一q a ) ( 佗一1 ) 。+ ( + q 一2 ) n p - ) ( 扎一1 ) 口 = ( z n + ( 佗一1 ) n ) ( + q 一2 ) q + 2 口一矿一q a ) 图2 “i 譬户一2 “l 气t ，夕二：? 一2 、( 、j 、 l 一一一：一一 v 12屹 u ，一2 g 一“o 设f ( p ，q ) = + q 一2 ) 。+ 2 。一矿一矿我们只需考虑f ( p ，q ) 的最小值 ，1 一 一、k n 等。 飞 一 6 h ： 准树图的最大广义r a n d i 5 指标 7 当p 0 ，q 0 ，o t 1 时，根据二项式展开不难看出f ( p ，q ) 0 ，而且当 n = l 时恰有，0 ，g ) = 0 口 根据引理2 2 1 ，我们可以得出，当a 1 ，g 的最大的广义r a n d i 6 指标就 取决于图g u o 是个星还是个双星 定理2 2 1设g q t ( n ) ，当o l 1 时，我们有r ( g ) ( 佗一1 ) 孙+ 2 ( 仡一2 ) 2 n ( 佗一1 ) 口，等式成立当且仅当g 兰畿 证明根据性质2 1 1 我们只需考虑d o = n 一1 由引理2 2 1 ，我们可以知道拥有最大的广义r a n d i d 指标的准树图g 必有 g 一缸。是个星或者是个双星于是，我们设g 一铷是个双星设钞1 ， v 2 v ( g ) 一u o ，v l v 2 e ( g ) ，d ( v 1 ) = p ，d ( 秽2 ) = q ，则2 q p 礼一1 且 p + q = n + 1 由定义 风( g ) = ( 矿+ q c , ) ( 佗一1 ) n + 矿g a + 0 2 ) 2 n 矿 + ( g 一2 ) 2 n q a + ( n 一3 ) 2 q ( 礼一1 ) n = ( 矿+ ( n p + 1 ) q ) ( 佗一1 ) a + 矿( n p + 1 ) + 一2 ) 2 。矿 + ( 死一p 一1 ) 2 。( 扎一p + 1 ) 口+ ( n 一3 ) 2 。( 礼一1 ) 口 = g ( p 1 现在对夕) 求导； 一q 【( 矿一q , 1 - i ) 一1 ) 口+ 矿。矿一矿矿以】 + p ( a + 1 ) 一2 a 2 n 矿一1 一 g ( q + 1 ) 一2 c q 2 。q 一1 ， 这里p + q = 佗+ 1 设p = q ，则有g = 0 准树图的最大广义r a n d i 指标 假设p q ，当口 1 时则乜+ l 2 ，我们有 8 9 7 q 旷一q q 。) ( n 1 ) n + p - 。q 口一矿q 0 - 1 】 = o 旷一1 一g n 一1 ) ( n 一1 ) a + ( 够尸一2 一矿一1 ) p 旷一1 】 a ( 矿一9 0 - 1 ) ( n 一1 ) n + ( g n 一矿_ 1 ) 鲫一1 】 = o 扩一1 一q a - 1 ) ( ( 佗一1 ) 口一p q 。一1 ) 因此，当q l 且p q 时，有夕7 0 ；当a = 1 时，夕，= 0 故夕m 馘( p ) = g ( n 一1 ) = ( n 一1 ) 驰+ 2 ( n 一2 ) 2 。( 佗一1 ) = 风( 畿一2 ) 显然 等号成立当且仅当g 竺嚣 口 第三章q 0 3 1 口 r ( 丁) ( 见图6 ) 口 图6 不难观察到如果在引理3 1 1 中t q t ( n ) ，那么r q t ( n ) ，所以引理 3 1 1 对q t ( n ) 中的图也是成立的也就是说n 2 。g q + 2 n ( d 一1 ) 口一矿一d a q 口 0 ， 其中d 4 ，l q 2 ，o z 0 口 引理3 1 3 1 8 】方程2 4 。一3 0 一9 。= 0 有唯一的负根一2 0 6 8 4 ，而 且，当p q o ；当a p 时，有2x 铲一3 0 一旷 0 注意到2 x 4 一3 - 1 - 6 - 1 = 0 ，类似于引理3 1 3 可以证明方程2 铲一3 a 一 一 j 准树图的最大广义r a n d i 6 指标 1 2 6 0 = 0 有唯一的负根o = - 1 ，而且，当- 1 q 0 ； 当a - 1 时，有2 铲一铲一铲 0 口 引理3 1 4 设图g q t ( n ) ，v p v ，u e ( g ) 假设a ( u ) = 3 且n ( u ) 秽) = 乱1 ，仳2 ) 如果当o l 0 时，g 是个m a x - q t ，那么 u l u 2 e ( g ) 证明用反证法 假设l z l ? t 2 不是e ( g ) 中的元素。 由连通性知，乱与u o 是不同的点设d ( u a ) = p ，d ( u 2 ) = q ，不妨设p q 臼弓i 理3 1 。l ，我们只须考虑p 2 情形1- 1 a 0 一一 。s 、 h 二一一，卜一一_ 一一 一” v u u 2 g 图8 如果p 3 ，那么g 中就会存在条新边u t v 7 ，使u t v 是g u o 的条悬挂 堑一 准树图的最大广义r a n d i d 指标 1 3 边设在g 中d ( u 7 ) = 如果在g 中d ( 7 ) = 2 ，即u o 秒7 e ( g ) 令g ，= g u u l u 乱2 一u o v t + ? 2 1 t t 2 + u v + u o v ，则g ，q t ( n ) ( 见图9 ) ，且 “l g l - 0 一一一 ， 图9 = ( g 7 ) 一r ( g ) = 2 4 。+ p a q 口一3 口一3 。矿一矿 = 2 4 。一3 口一9 口+ 扩一3 a ) ( q a 一3 a ) 2 4 n 一3 口一9 0 当- 1 a 0 。否则，在g 中就会有 d ( v 7 ) = 1 且d 7 2 令= g u u l 一让钍2 + “1 t 正2 + u v t ( 见图1 0 ) ，则 g ，q t ( n ) 且 风( g ) 一心( g ) = 2 。+ 铲+ ( 2 口一1 ) ( ) 口+ 矿g q 一3 a 一3 口矿一3 & ， 2 a + 4 q + ( 2 n 一1 ) 2 。+ 矿q 。一3 口一酽矿一3 n 口n = a 0 其中一1 a 0 、i 、 一 一y 眨 i j _ y 如 ；：、_ ， ， ， 一 ，、|，_ 弋 “i 、 1 + 、 _ - 一 ，7材y u o g 情形2q 一1 一一c _ y“ 图1 0 令= g 一缸1 牡+ 让1 乱2 q t ( n ) ( 见图1 1 ) 且= 忍( g ，) 一忍( g ) g c 、) 斗二卜 v “ u 2 如果p = q = 2 设n ( u i ) 钍) = 加i ) ，d ( w i ) = d i ，其中i = 1 ，2 由连通 性，有d x 2 或者如2 不妨设奶2 ，否则，我们便令d = g u 2 u + u l 札2 q t ( n ) ，则当a 0 一 入 _ 一 s一2 厂 、够 臣一 准树图的最大广义r a n d i d 指标 1 5 如果q 3 ，由引理3 1 1 和引理3 1 2 知，在m a x q t 中至少存在个与 u 2 相邻的一度点所以当o 2 n 一3 q + 2 a ( ( g + 1 ) 口一3 a ) + ( ( g + 1 ) 。一矿) 1 + ( q 一2 ) 2 口】 = 2 n 一3 口一6 a + ( ( 口+ 1 ) a g q ) ( 1 2x2 n ) + 2 口( ( g + 1 ) n + 1 一q 口+ 1 ) = ，( q ) ， 且 ，7 ( g ) = a ( ( g + 1 ) n 一1 一矿一1 ) ( 1 2 。+ 1 ) + ( a + 1 ) 2 。( ( g + 1 ) 。一q 。) 0 ， 这里位 2 n 一3 口一6 口+ ( 3 口一2 。) ( 1 2 n + 1 ) + 2 n ( 3 口+ 1 2 口+ 1 ) = ( 2 1 = 0 从而当口 0 口 引理3 1 5令g q t ( n ) ，设p = x u l 乱t y 是g 的一条路，z y 不 是g 中的边，其中d ( x ) = p 3 ，d ( y ) = q 3 ，d ( u 1 ) = = d ( u t ) = 2 ， u o 1 i t 如果存在个点v p y 且它的邻点u 的度不超过3 ，那么 令g 7 = g x u l y u + x y + v u l q t ( n ) ，贝4 当q 忍( g ) 准树图的最大广义r a n d i d 指标 证明设d ( u ) = d 2 ，则 1 6 亿( g 7 ) 一凰( g ) = p a q 。+ 矿+ 2 a 矿一矿一2 q 矿一矿矿 = ( 酽一矿) ( 2 口一矿) + ( 2 q e f t ) ( 1 一垆) 0 ， 其中口 0 口 设p = u l u 2 u ，是条路，u i y ( g ) ，1 i r 。如果d ( u 1 ) = 1 ， d ( u i ) = 2 ，i = 2 ，7 一l 且d ( u ，) 3 ，则我们称尸是条以u ，为根的悬挂 路，其中? 一1 称为这条悬挂路的长度特别的，当r = 2 时，这条悬挂路就是 条悬挂边 总结以上我们得到以下性质： 性质3 1 1当a 0 时，设g 是个m a x q t ，如果p y 仍，则 ( 1 ) 任意的v p y 的邻点，除了至多有个是与u o 相邻的3 度点，其 余的都是2 度点； ( 2 ) 如果d ；0 2 ，那么每个2 度点必须出现在悬挂路上 口 3 2q - 2 1 时的极图 引理3 2 1 设q - 2 1 ，n 7 ，g 夷 个m a x q t ，则 ( 1 ) d o = 2 ： ( 2 ) p y 仍； ( 3 ) 除了钍。和至多个与u o 相邻的点外，每个2 度点都在悬挂路上； ( 4 ) 要么除了至多有条悬挂边u v 满足? d u o e ( g ) 且d ( u ) = 3 ，要么 除了至多有条长是3 的悬挂路且u o 的邻点都不是2 度点，其它所有的悬挂路 的路长都是2 准树图的最大广义r a n d i d 指标 1 7 证明( 1 ) 用反证法 假设d o 3 设n ( u o ) = 仳l ，钍d 0 ，d ( u i ) = d i ，1 i d o ，d l d a o 用& 表 示所有与u 相关联的边的权之和，除了u o u i 和u i u j ，如果札t e ( g ) ，这里 i 粥调一善d o 簖露一薹d o & ( 竿_ 1 ) 矿( 砰+ 霹) 一簖露一& ( 警一1 ) 2 n ( 四+ ) 一诺露 = ( 2 口一豸) ( 贯+ ) 一喀 i - - - - 3 2 ( 2 a d g o ) 一( d 0 2 ) 前 = ( 2 叶1 一簖“) d g o 0 ， 与g 是个m a x q t 矛盾 ( 2 ) 如果p y = 0 ，那么有( 1 ) 可以知道g 是个圈u o u l “n - - 1 令 g ，= g 一仳o u 。一1 + u o u 2 q t ( n ) ，由于a 2 n 一4x 矿 = 2 。( 1 4x2 。) 0 准树图的最大广义r a n d i 6 指标 1 8 ( 3 ) 设p = w u u o u l 是f 中条路，且d ( 乱) = d ( 乱1 ) = d o = 2 令 g ，= g w u 一 a o u l + w u o + u u l ，则g ，q t ( n ) ( 见图1 2 ) 显然广义r a n d i d 指标值没有发生变化根据引理3 1 5 ，我们只须作如下证明 f 7 广、j 一1i 一卜一- 卜 、，w u l ou l 、 g 设p = u o u l u 2 u ，( r 3 ) 是g 中的条路，满足d ( u o ) = = d ( u ，一1 ) = 2 ，d ( u ，) = d 2 由连通性可知d 3 如果u o u ，不是g 的边，由引理3 1 2 和3 1 4 ，不存在与u ，相邻的1 度点， 所以& ，dx2 0 扩令g ，= g 一咖u 1 + u o u ，( 见图1 3 ) ，则g ，q t ( n ) 且 风( g 7 ) 一心( g ) = ，( 堕去娑一1 ) + 2 。一4 口+ 2 。( ( d + 1 ) 口一矿) dx2 。( ( d + 1 ) 口一矿) + 2 口一4 q + 2 n ( ( d + 1 ) 口一2 n ) = 2 q 【( 1 2 n + 1 ) 一( d a + 1 一( d + 1 ) n + 1 ) 】 0 这是因为在o 0 ， 其中q - 2 1 如果r 4 ，当o l 一2 1 时，有 忍( g ) 一忍( g ) = 2 口+ 6 。+ ( 3 。一2 口) 矿一2 4 。 2 口+ 6 口+ ( 3 0 一2 口) 3 a 一2 4 a = 2 口牟9 0 一2x4 a 3 8 + 9 口一2x4 口 0 ( 4 ) 设p = u l z t 2 u ，是g 的条悬挂路，其中r 5 ，d ( u ，) = d 3 由引理3 1 2 和3 1 4 可知g 中没有与u ，相邻的1 度点否则，我们有 u o u ，e ( g ) 和西3 ，这时图g u o 不连通，矛盾所以鼠，dx2 a 矿令 g = g u 2 u 3 + u 2 u ，则g ，q t ( n ) 且 见( g 7 ) 一见( g ) = 穿+ 2 a ( d + 1 ) a 一4 n 一矿+ & ，( 鱼专芒一1 ) 2 。+ 2 。( d + 1 ) 。一2x4 。+ d 2 。( ( d + 1 ) 。一扩) = 2 。 ( d + 1 ) 。+ 1 一矿+ 1 + ( 1 2 。+ 1 ) 】 = 厂( d ) 令g ( x ) = z 口+ 1 一( z + 1 ) 叶1 当a y ( d ) 0 如果g 有两条长为3 的悬挂路只= u 1 札2 仳3 u 4 和p 2 = 硼1 w 2 w 3 w 4 我们删 掉边u l u 2 并把u l 与w l 连接，则这个新图q t ( n ) 且只有条长为3 的悬挂 路显然，此时广义r a n d i d 指标没有发生变化 如果g 只有一条长为3 的悬挂路p = u l u 2 u 3 u 4 设钍n ( u o ) ，d ( u ) = 2 ， n ( u ) = ，叫 由( 3 ) 知d ( w ) 3 令g ，= g u l l l , 2 + u u l q t ( n ) ，则 风( g ) 一忍( g ) = 3 。+ 6 。+ ( 3 。一2 n ) 矿( 伽) 一4 n 一4 。 3 0 + 9 0 一2 铲 0 其中口一2 1 设u v ，u u o e ( g ) ，d ( v ) = 1 ，那么d ( u ) = 3 ，令g ，= g u l u 2 + u l v q t ( n ) ，贝0 r ( g ) 一凤( g ) = 2 q + 6 n 一3 a 一4 0 = ( 1 2 口) ( 2 q 一3 口) 0 ， 其中q a ( q + 1 ) 妇+ q 一2 ) 口一1 一矿一1 q a 一1 】 0 ， 塞，2 ) = 2 。+ 1 ) 矿一( a + 1 ) 矿+ 叩一1 】- 甜矿_ 1 = 0 ， 故器( p ，g ) 0 又因为当q 一2 1 ，p ，q 3 时， 知g ) = 2 冰a + 1 ) 口口小+ 1 ) 2 a + a 2 a - 1 h g n = ( 2 + 0 ) 2 a - - 1 ( q 8 2 n ) 0 ， 故9 ( p ，q ) 0 如果u o u ，一1 不属于e ( g ) ，则d ( u ，一1 ) = d ( w 1 ) = = d ( w q 一2 ) = 2 ，且 2 = 风( g ，) 一风( g ) = 1 + 4 口一6 口一( 2 n 一3 口) g 口 = 1 + ( 矿一3 口) ( 矿一矿) 1 0 情形2 如果u o u ，一2 e ( g ) 设n ( u ，一2 ) 【o ，u r 一3 ，u ，一1 ) = w 1 ，w q 一3 ) ， g 7 = g 一“r 一2 w 1 一一u r 一2 w q 一3 + t 正r 一3 w a + + 乱r 一3 w q 一3 一u r 一1 u r 一2 + u r 一1 u r 一3 ， 则g q t ( n ) ( 见图1 6 ) 当q 一2 1 时，有 “0 r 0 ?r 准树图的最大广义r a n d i 6 指标 无论是哪种情形，我们都得到矛盾 如果g 中存在条长是3 的悬挂路设p = u l u 2 坼是g 一扎。中以钍1 为起点的最长的路，且使d ( u r - 1 ) 在g 尽可能的大，及u ，u r 一1 u r - 2 t l , r 一3 不是长 为3 的悬挂路由以上证明，g ，中存在个点，这个点要么是与u o 相邻的2 度点，要么是满足u ? j e ( g ，) 的1 度点按照引理3 2 1 ( 4 ) 的证明，我们 从图d 中得到个新图d 7 q t ( n ) ，且在g ，中没有长为3 的悬挂路此定 理证毕 口 准树图的最大广义r a n d i 6 指标 r e f e f e n c e s 参考文献 1 】m r a n d i 6 ，o nc h a r a c t e r i z a t i o no fm o l e c u l a rb r a n c h i n g ，j a m e r c h e m s o c 9 7 ( 1 9 7 5 ) 6 6 0 9 6 6 1 5 【2 l b k i e ra n dl h h a l l ，m o l e c u l a rc o n n e c t i v i t yi nc h e m i s t r ya n d d r u gr e s e a r c h ，a c a d e m i cp r e s s ，n e wy o r k ，1 9 7 6 3 】3n t r i n a j s t i 6 ，c h e m i c a lg r a p ht h e o r y , c r cp r e s s ，b o c ar a t o n ，f l ， 1 9 9 2 【4 o a r a u j oa n dj a d el ap e f i a ，t h ec o n n e c t i v i t yi n d e xo faw e i g h t e d g r a p h ，l i n e a ra l g e b r aa p p l 2 8 3 ( 1 9 9 8 ) 1 7 1 1 7 7 【5 】l b k i e ra n dl h h a l l ，t h en a t u r eo fs 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 sa n dt h e i rr e l a t i o nt om o l e c u l a rc o n n e c t i v i t y e u r o p e a nj m e d c h e m 1 2 ( 1 9 7 7 ) 3 0 3 1 2 【6 b b o l l o b 自sa n dp e r d s s ，g r a p h sw i t he x t r e m a lw e i g h t s a r sc o r n - b i n 5 0 ( 1 9 9 8 ) ，2 2 5 2 3 3 7 】d a m i 6 d b e s l o ，b l u 己i 6 ，s n i k o l i 6a n dn t r i n a j s t i 6 ，t h ev e r t e x - c o n n e c t i v i t yi n d e xr e v i s i t e d ，j c h e m i n f c o m p u t s c i 3 8 ( 1 9 9 8 ) 8 1 9 8 2 2 【8 p y u ，a nu p p e rb o u n do nt h er a n d i 6i n d e xo ft r e e s ，j m a t h s t u d y ( i nc h i n e s e ) 3 1 ( 1 9 9 8 ) 2 2 5 2 3 0 准树图的最大广义r a n d i 6 指标 2 7 【9 】g c a p o r o s s i ，i ，g u t m a n ，p h a n s e na n dl p a v l o v i 6 ，g r a p h sw i t h m a x i m u mc o n n e c t i v i t yi n d e x ，c o m p u t b i 0 1 c h e m 2 7 ( 2 0 0 3 ) 8 5 - 9 0 【l o 】l h c l a r ka n dj w m o o n ，o nt h eg e n e r a ll h n d i 6i n d e xf o rc e r t a i n f a m i l i e so ft r e e s ，a r sc o m b i n 5 4 ( 2 0 0 0 ) 2 2 3 - 2 3 5 1 l 】y h u ，x l ia n dy y u a n ，s o l u t i o n st ot o wu n s o l v e dq u e s t i o n so n t h eb e s tu p p e rb o u n df o rt h er a n d i 6i n d e xr 一1o ft r e e s ，m a t c h c o m m u n m a t h c o m p u t c h e m 5 4 ( 2 0 0 5 ) 4 4 1 4 5 4 1 2 】g c a p o r o s s i ，i g u t m a na n dp h a n s e n ，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 s4 ：c h e m i c a lt r e e sw i t he x t r e m a lc o n n e c t i v i t yi n d e x ，c o m p a n dc h e m 2 3 ( 1 9 9 9 ) 4 6 9 4 7 7 【1 3 】x l ia n dy y a n g ，o nt h el o w e ra n du p p e rb o u n d sf o rg e n e r a lr a n d i 6 i n d e xo fc h e m i c a l ( n ，m ) 一g r a p h s ，m a t c hc o m m u n m a t h c o m p u t c h e m 5 2 ( 2 0 0 4 ) 1 5 7 - 1 6 6 1 4 】x l ia n dy y a n g ，s h a r pb o u n d sf o rt h eg e n e r a lr a n d i 6i n d e x ， m a t c hc o m m u n m a t h c o m p u t c h e m 5 1 ( 2 0 0 4 ) 1 5 5 1 6 6 1 5 】y h u ，x l ia n dy y u a n ，t r e e sw i t hm i n i m u mg e n e r a lr a n d i 6i n d e x ， m a t c hc o m m u n m a t h c o m p u t c h e m 5 2 ( 2 0 0 4 ) 11 9 1 2 8 【1 6 】y h u ，x l ia n dy y u a n ，t r e e sw i t hm a x i m u mg e n e r a lr a n d i 6 i n d e x m a t c hc o m m u n m a t h c o m p u t c h e m 5 2 ( 2 0 0 4 ) 1 2 9 1 4 6 17 】x p a n ，h l i ua n dj x u ，s h a r pl o w e rb o u n d sf o rt h eg e n e r a lr a n d i 6 i n d e xo ft r e e sw i t hag i v e ns i z eo fm a t c h i n g ，m a t c hc o m m u n m a t h c o m p u t c h e m 5 4 ( 2 0 0 5 ) 4 6 5 4 8 0 准树图的最大广义r a n d i 指标 1 8 】x c h e na n dj q i a n ，c o n j u g a t e dt r e e sw i t hm i n i m u mg e n e r a l r a n d i di n d e x ，d i s c r e t ea p p l m a t h 1 5 7 ( 2 0 0 9 ) 1 3 7 9 1 3 8 6 【1 9 】m l ua n dj g a o ，o nt h er a n d i di n d e xo fq u a s i t r e eg r a p h s ，j m a t h c h e m 4 2 ( 2 0 0 7 ) 2 9 3 1 0 【2 0 m f i s c h e r m a n n a h o f f m a n n ，d r a n t e n b a c ha n dl v o l k m a n n ， a l i n e a r p r o g r a m m i n ga p p r o a c ht ot h eg e n e r a lr a n d i 6i n d e x ，d i s c a p p l m a t h 1 2 8 ( 2 0 0 3 ) 3 7 5 3 8 5 【2 1 i g u t m a n o m i l i j k o v i d ，g g a p o r o s s ia n dp h a n s e n ，a l k a n e sw i t h s m a l la n dl a r g er a n d i dc o n n e c t i v i t yi n d i c e s ，c h e m p h y s l e t t 3 0 6 ( 1 9 9 9 ) 3 6 6 - 3 7 2 【2 2 】p h a n s e na n dh m 6 1 0 t ，v a r i a b l en e i g h b o r h o o ds e a r c hf o ee x t r e m a l g r 印l l 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 s c i 4 3 ( 2 0 0 3 ) 1 1 4 【2 3 1x l ia n dj z h e n g ，e x t r e m a lc h e m i c a lt r e e sw i t hm i n i m u mo r m a x i m u mg e n e r a lr a n d i di n d e x ，m a t c hc o m m u n m a t h c o p m u t c h e m 5 5 ( 2 0 0 6 ) 3 8 1 3 9 0 2 4 】m l u ，l z h a n ga n ff t i a n ，o nt h er a n d i do f