（基础数学专业论文）单圈图的wiener指数.pdf

单圈图的w i e n e r 指数 0 1 中文摘要 设g = ( ke ) 是一个简单连通图，y 和e 分别为g 的顶点集和边 集。那么，g 的w i e n e r 指数w ( g ) 是指图g 中所有顶点对之间的距 离之和，即 w ( g ) = d a ( u ，口) t 工，”) g 其中d a ( u ，口) 表示g 中顶点“和口之间的距离。w i e n e r 指数是化学 图论中经典的拓扑指数( 图不变量) 之一，并已被证实在定量结构一 活性性质相关性( q s a r q s p r ) 中是一个非常有用的量；同时， w i e n e r 指数也被用于通讯网络的研究。 本文我们研究单圈图的w i e n e r 指数。首先，根据单圈图结构，我 们给出了单圈图w i e n e r 指数的一个计算公式；然后，利用这个计算 公式，刻划了具有最大、最小、次大、次小、第三大、第三小w i e n e r 指数的单圈图的特征。 关键词：单圈图、w i e n e r 指数、距离、极值图 i i 湖南师范大学高校教师硕士论文 0 2 a b s t r a c t l e tg = ( k e ) b eas i m p l ec o n n e c t e dg r a p hw i t hv e r t e xs e tva n de d g es e t e t h ew i e n e ri n d e xw ( a ) o fgi st h es u mo fd i s t a n c e sb e t w e e na l lp a i r so fv e r t i c e s i ng ，i e ， w ( g ) = d a ( u ，u ) u ， ) g w h e r ed a ( u ， ) i st h ed i s t a n c eb e t w e e nv e r t i c e sua n dui ng w i e n e ri n d e xi so n e o ft h ec l a s s i ct o p o l o g i c a li n d i c e s ( g r a p hi n v a r i a n t s ) i nc h e m i c a lg r a p ht h e o r y i th a s b e e ns u c c e s s f u l l yu s e di nt h e o r e t i c a lc h e m i s t r yf o rq 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 y r e l a t i o n s ( q s p r ) a n dq 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 ( q s a r ) ，a n da l s o i ns t u d y i n gc o m m u n i c a t i o nn e t w o r k s i nt h i sp a p e r ，w es t u d yt 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 s f r i s t l y ，w eg i v e af o r m u l a t i o nf o rc a l c u l a t i n gt h ew i e n e ri n d e xo fa nu n i c y c l i cg r a p ha c c o r d i n gi t s s t r u c t i o n a n dt h e n ，u s i n gt h i sf o r m u l a t i o n ，w ec h a r a c t e r i z et h eg r a p h sw i t ht h e l a r g e s t ，t h es m a l l e s t ，t h es e c o n dl a r g e s t ，t h es e c o n ds m a l l e s t ，t h et h i r dl a r g e s ta n d t h et h i r ds m a l l e s tw i e n e ri n d i c e sa m o n ga l lt h eu n i c y c l i cg r a p h so fo r d e rn k e yw o r d ：u n i c y c l i cg r a p h ，w i e n e ri n d e x ，d i s t a n c e ( i n ag r a p h ) ，e x t r e m a l g r a p h 单圈图的w i e n e r 指数 第一章单圈图w i e n e r 指数 图论已广泛应用于诸多学科领域，如计算机科学、通讯工程、 物理学、工业管理、心理学及社会学等，但是重要的应用领域应首 推化学学科。在化学中，已有的应用涉及合成化学、聚合化学、量 子化学及化学信息的存储和检索等。近年来，最大量的应用集中在 定量结构一活性性质相关性( q s a r q s p r ) 的研究方面。 当今，在生物学、药物学、毒物学和环境科学中一个很重要的 发展趋势是将分子生物活性性质的定量预测用于分子设计。据估 计，大约从1 0 0 0 0 个化合物中才能够筛选出一个作为有效药物投入临 床使用。以往凭经验由母体化合物衍生同源化合物的效率很低，因 而促使人们去寻找更优的来创制新药。与此类似，在工业和环境科 学中，每年要测试( 毒性、致突变、致癌等) 和处理的化合物多达 数十万种，若仅靠实验将耗费极大的人力物力，所以必须有新的方 法才能满足客观需要。q s a r q s p r 方法为我们提供了一条可行的途 径。目前已涌现出了诸多q s a r q s p r 方法，其中图论方法有其独特 的优点，因为这类方法仅依赖于分子结构，即由结构图可以直接衍 生结构特征。拓扑指数就是从化合物的结构图衍生出来的一种数学 不变量。 大约在一百多年之前就引入了拓扑指数，至今已有1 2 0 多种被 证实在结构活性性质相关性( q s a r q s p r ) 中非常有用，w i e n e r 指数就是其中一个很经典的拓扑指数，它是化学家h w i e n e r 1 在引入 的一个拓扑指数。在1 9 4 7 年至1 9 4 8 年间，h w i e n e r 根据碳原子之间路 径距离的计数，提出了一个刻划分子结构的指数w ，他倡导性地利 用w 研究了饱和碳氢化合物的分子结构与物理性质( 沸点、摩尔体 积、折射率、烷烃异构与蒸发热等) 之间的关系。由于在当时化学图 形论尚未形成，因此，h w i e n e r 未利用图论专业术语。h o s o y a 在1 9 7 1 年文献 2 中给出了一个用图论术语表述的公式，即w i e n e r 指数等于 碳氢化合物中所有最短碳一碳键路径之和。为纪念w i e n e r 的贡献，把 图中两点间的距离之和称为w i e n e r 指数或w i e n e r 数；w i e n e r 指数已 湖南师范大学高校教师硕士论文 被证实在定量结构一关系( q s p r ) 中是一个非常有用的量 2 7 】，同 时也被用于通讯网络的研究【8 , 9 。 从1 9 7 0 年代中期开始，w i e n e r 指数得到了非常广泛的研究。从 此以后，新的结果不断涌现；有关w i e n e r 指数在化学中应用的详细历 史背景和进一步的文献资料参见 5 , 6 ，1 0 。由于很长b e i 日- 内，数学家并 不知道化学中有关w i e n e r 指数较早期的工作，在数学文献中w i e n e r 指数研究似乎始于1 9 7 6 年f 1 1 。数学中w i e n e r 指数也称为图的距离 或传输 1 1 ，1 2 ，同时，许多数学论文中研究的是一个与w i e n e r 指数 密切相关的不变量一平均距离 1 3 】。 关于w i e n e r 指数的理论长期以来有这样一些问题引起研究者的 关注：( 1 ) w ( g ) 是怎样依赖于g 的结构；( 2 ) 怎样有效的计算w ( g ) ( 包括所谓的“纸和笔”的方法) ；( 3 ) 在一些特殊图类中( 尤其是 化学图) 中具有最大、最小( g ) 的图；( 4 ) 在一些特殊图类依w i e n e r 指数的排序。对于树与六角形系统，这方面的研究已取得很大的进 展，有关结果综述在文献 1 4 ，1 5 中。近些年来，国内外许多研究者 给出了一些分子结构图或特殊图类( 如树，多边形系统，瓯和q 瓯 纤维管等) w i e n e r 指数各种各样的算法 1 6 1 9 ，刻划了一些图类中 极图的特征和排序【2 0 ，2 1 ，2 2 ；研究了w i e n e r 指数的逆问题、等可分 树( 分子图) 和图中保w i e n e r 指数的树等 2 3 3 0 】，以及w i e n e r 指数 的推广 3 1 3 5 】。 本文我们研究单圈图的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 1 2 单圈图w i e n e r 指数的计算 本文所涉及的图都是连通的简单无向图一个图g 的顶点集和 边集分别是v ( a ) 和e ( a ) ，g 的顶点数用n ( g ) 表示，称为g 的阶。 顶点u 和v 之间的距离d c ( u ，u ) 是指g 中连接顶点乱和u 之间的最短 路径上的边的数目。一个顶点u 的距离d a ( u ) 是指 与g 中所有其它 顶点之间的一个图距离之和，即d a ( ) = d av ，z ) w i e n e r 指数是 z v ( g ) 基于图中距离的不变量，用w ( g ) 表示，它的定义 2 为g 中所有顶 点对这间的距离之和： w ( g ) = d a ( u ，u ) ( 1 ) t 工，u ) y ( g ) 也可表示为 d ( g ) = i x i ( 2 ) i = 1 其中z i 表示距离为i 的顶点对个数，d 为图的直径 设g = ( ke ) 是一个n 阶单圈图，其中圈c m ：v l u ：u m 勘。的长度 为m ，则g e ( c m ) 的非平凡连通分枝乃，噩，t k ( 0 k m ) 都是非 平凡树。互与的公共顶点u i 称为t i 的挂点，i = 1 ，2 ，k 这样 的单圈图g ，我们用g = 嘴m ，u t ( 丑，t 2 ，孔) 来表示；若令礼( 互) = 如+ l ，则1 = n m = 1 1 + 1 2 + 1 3 + + l 七。特别，对于单圈图g 1 = c 鬻一2 ，一( & 1 + l ，鼠2 + 1 ，& + 1 ) 和g 2 = 饼舢2 m “( 蜀，+ 1 ，r 2 + l ，局b + 1 ) ， 顶点u 2 ，u 惫在g 。中分别是岛，+ 1 岛。扎，s 。十1 的中心，而在g 2 中分别是毋，十1 毋。+ l ，毋的一个端点。k = 0 时，g = g 是一个 长为n 的圈；k = 1 ，m = 3 时，喏( 岛一2 ) 就是岛+ e ，并将四- ( r 一2 ) 简记为侥( r 一2 ) 。 为了计算礼阶单圈图g 的w i e n e r 指数，我们需要了解有关特殊 树的w i e n e r 指数的一些结果。 引理1 ( ( 1 5 】) 缈( r ) ：fn ：11 ，( 又) ：( n 一1 ) 2 ，其中r 为礼个 5 顶点的路，岛为扎个顶点的星图；且对于任意不同于r 和品的n 阶树t ，有( 鼠) w ( t ) 彬( r ) 湖南师范大学高校教师硕士论文 设u 是礼阶树t 的一个分枝点( 即度大于2 的顶点) ，如( u ) = m 3 ，t 一 u ) 的连通分枝为孔，噩，t m ，若死的阶数为n ( 互) = i = 1 ，2 ，一，m ，贝0 有礼1 + n 2 + + 礼m = n 一1 引理2 ( 1 5 ) 设t 是阶为礼的树，则 咿，= 1 ) y 聊e 其中求和取遍t 的所有分枝点，求和取遍t 一( 乱) 的所 u 1 i j w ( c 蔫l 1 ( 一m + 2 ) ) 。 证明由定理4 得 w ( 嘴( & 一m + 1 ) ) 一( 瞟1 ( 品一m + 2 ) ) = 缈( ) + ( n m ) d g m ( 让) + ( m 一1 ) ( 礼一m ) 十缈( & 一m + 1 ) 一 w ( c m 一1 ) + ( n m + 1 ) d c m 一，( u ) + ( m 一2 ) ( n m + 1 ) + w ( 一m + 2 ) 当m 是奇数时，由引理1 和3 知 w ( 罐( 岛一m + 1 ) ) 一( 罐1 ( 品一m + 2 ) ) = ；m ( m 2 1 ) + ( 钆一m ) ( m 2 一1 ) + ( m 1 ) ( n m ) + ( n m ) 2 j 一 ( m 1 ) 3 + ( n m + 1 ) ( m 一1 ) 2 + ( m 一2 ) ( 礼一m + 1 ) + ( n m + 1 ) 2 = 1 7 7 2 7 1 3 7 t 2 , 2 + m 一；札+ ； = m 2 + ( ；t 一1 ) m + ( ；一；t ) ( 其中t = n m ) 0 ( 因m 3 且t 0 ) 引成证 七 o 湖南师范大学高校教师硕士论文 当m 是偶数时，类似可证 ( 嘴( 品一m + 1 ) ) 一w ( c 蔫l 1 ( s n - m + 2 ) ) 0 因此，当m 3 时， ( 嘴( 晶一仇+ 1 ) ) ( 啡1 ( 岛一m + 2 ) ) 定理8 设g = 嘴，m ( t 1 ，t 2 ，死) 是一个礼阶单圈图，则 ( g ) ( 晶+ e ) 且等号成立当且仅当：( i ) 凡：4 时，g 掣q 或& + e ；( i j ) n ：5 时， g 竺6 5 或& + e ；( i i i ) n 6 时，g 竺岛+ e 。因而，具有最小w i e n e r 指数 的单圈图是瓯，既和晶+ e ，其中& + e 表示在星图品中添加任意一 条边所得到的单圈图。 证明由定理4 可计算出w ( s n + e ) ：? 2 2 2 n 若k = 0 ，即g = g 本身是一个圈，则当礼为偶数时， w ( g ) 一w ( + e ) = 言n 3 一( n 2 2 几) = 去n ( n 一4 ) 2 o 且等号成立当且仅当n = 4 ；当饥为奇数时， 彬( ) w ( & + e ) = 击仃( 礼2 1 ) 一( 凡2 2 扎) = 去扎( 佗一3 ) ( 扎一5 ) 0 且等号成立当且仅当n = 3 ，5 。 若k l ，由推论5 ，引理6 知，彬( g ) 2 彬( 罐( 品一m + 1 ) ) 。 其次，若m 3 ，由引理7 得， ( 罐( s n m + 1 ) ) w ( 鼹1 ( s t , 一m + 2 ) ) 故w ( g ) ( 四1 ( 品一2 ) ) = w ( 岛+ e ) ，且等号成立当且仅当g 竺& + e ，定 理8 得证。 单圈图的w i e n e r 指数 9 2 2 单圈图w i e n e r 指数的最大值 这一节我们给出礼阶单圈图g ：( v e ) 的w i e n e r 指数的最大值 并刻划出n 阶单圈图中具有最大w i e n e r 指数的图的特征。 引理9 设g 2 = 镄，让2 ，m ( 蜀，+ 1 ，蜀。+ 1 ，局。+ 1 ) ，则w ( a 2 ) ( 嘴( 蜀+ 1 ) ) ， 其中忙1 1 + f 2 + + l 七，且等号成立当且仅当尼= 1 ，即g 2 笺勰( 局+ 1 ) 。 证明由引理l 和定理4 知 ( 铹( 蜀+ 1 ) ) 一w ( g 2 ) 叩c 啪卜咖小叫”2 + 州，+ 2 ) ， 叩( n _ m ) 川m _ 1 ) 量k ( 1 + + 删+ 量k 2( 如；2 ) 一 ( g f m ) + ( n m ) u + ( m 一1 ) ( 1 + + f i ) + 堇i冀j 2 = lz = 1 、 o ， k - 1 + i - - - 1 = i + i 1 i ( 1 + 2 + + 2 j ) + l i l j d c 。( u i ，u j ) + l j ( 1 + 2 + + z t ) ) ( m 一1 ) f ( c + 1 ) 一 k - 1 一 k2 i ( f i + 1 ) + 【( 1 3 + 3 1 2 + ) 一k 3 l 2 l ( 1 i + 3 l ；+ 2 1 i ) 】 2 i ( f i + 1 ) + 【( + +) 一( i +；+ 】 i = 1 t = l t j j ( z j + 1 ) + l i l j d c m ( u i ，呦) 十；l j l i ( 1 i + 1 ) i = 1j = i + 1 k 1 = ( m 1 ) ( i - - - - 1j = i 士1 ( 其中在求和 鸲) + l i l j l t i , i ，t 中i ，j ，t i , j ，t 遍历 凫一1七 一l i l j d c 。( u t ，u j ) i = 1 = i + i 1 ，2 ，后且i ，j ，t 互不相等) 七一1七 = l i l f l t + i d j ( m 1 ) 一d c m ( u i ，u j ) 】 i , j ，t i = 1j = i + l o 且等号成立当且仅当k = l ，即g 2 竺嘴( p l - - i ) 。 则 定理1 0 设g = g 船讹，一( 丑，码，一，乃) 是一个n ( n 4 ) 阶单圈图， w ( a ) ( 伤( p n 一2 ) ) 且等号成立当且仅当： ( i ) n = 4 时，g 竺c 4 或岛( b ) = & + e ；( i i ) n 4 时，g 竺岛( r 一。) 。因而，具有最大w i e n e r 指数的单圈图是c 4 和 仍( r 一2 ) 。 证明由定理4 可计算出w ( c 3 ( p n 一2 ) ) = 石1 、n 3 7 n + 1 2 ) 。 七 七 七 湖南师范大学高校教师硕士论文 若南= 0 ，即g = g 本身是一个圈，则当n 为偶数时， w ( c 3 ( p n 一2 ) ) 一w ( g ) 2 吉( 礼3 7 钆+ 1 2 ) 一言佗32 去( 扎3 2 8 几十4 8 ) o 且等号成立当且仅当礼= 4 ，此时有w ( c 4 ) = 形( 凸( p 2 ) ) ；当佗为奇数时， w ( c 3 ( p n 一2 ) ) 一w ( c n ) 。吉( 礼3 7 n + 1 2 ) 一言扎( 咒2 1 ) = 甄i ( n 3 2 5 竹+ 4 8 ) o 且等号成立当且仅当n = 3 。 若k 1 ，由推论5 和引理9 知，( g ) ( 罐( 局+ 。) ) ，且等号成立 当且仅当砖= 1 ，即g 笺勰( 毋+ 1 ) 。 其次，我们证明当m 4 时，( 嘴( r + 。) ) 冬彬( 岛( r 一2 ) ) ，其中 f = n 一”1 ( i ) 设m 是偶数，由引理1 , 3 和定理4 知， w ( c a l ( 蜀+ 1 ) ) = w ( c m ) + ( 7 1 一m ) d c 。( u ) + ( m 一1 ) ( 1 + 2 + + 1 ) + w ( 毋+ 】) = m 3 + m 2 ( n m ) + ( m 一1 ) ( 扎一m ) ( n m + 1 ) + ( n 一了+ 2 ) = 【礼3 + ( 一互3 m 2 + 3 m 一1 ) 礼+ ( ；m 3 3 m 2 + m ) w ( 仍( r 一2 ) ) 一w ( 铹( 毋+ ，) ) = 言【( 墨m 2 3 m 一6 ) 礼一( 石5 m 3 3 m 2 + m 一1 2 ) 又n m ，从而( ；m 2 3 m 一6 ) n 一( ；m 3 3 m 2 + m 1 2 ) w ( c 3 ( p n 一2 ) ) w ( c a , ( p z + 1 ) ) ，且等号成立当且仅当m = n = 4 。 0 ，故 ( i i ) 设m 是奇数，则类似地可证w ( c 3 ( p n 2 ) ) w ( c 辫( p z + 1 ) ) 。 由上可知，w ( g ) w ( c 3 ( p 一。) ) ，且等号成立当且仅当： ( i ) n = 4 时，g 兰。或c 3 ( p 2 ) ；( i i ) n 4 时，g 垒c 3 ( p n 一2 ) 。因而，具有最大 w i e n e r 指数的单圈图是q 和c 3 ( p n 一2 ) 。 当立成争等且 挖 一m+m 口u m 5 4 一 m 回 一m3 2 m 偿 以 4 4 一 | | m m 因当仅且 单圈图的w i e n e r 指数 1 1 第三章具有次大、次小w i e n e r 指数的单圈图 设g = c 鬻，u 。，u t ( 丑，t 2 ，巩) 是礼阶单圈图。当n = 3 时，单圈 图只有国；当n = 4 时，单圈图有q ，& + e ，则w ( c 4 ) = w ( s 4 + e ) = 8 ； 当n = 5 时，单圈图有五种即： 既，岛+ e ，c 4 ( p 2 ) ，掣1 ，伽( p 2 ，p 2 ) ，c 3 ( p 3 ) ，则 ( 岛) = w ( 岛+ e ) 5 ) 阶单圈图g = ( v e ) 的w i e n e r 指数的次 小值，并刻划出礼阶单圈图中具有次小w i e n e r 指数的图的特征。 定理1 1 设g = 础，u 2 ，m ( t 1 ，t 2 ，t k ) 喾s n + e 是一个n ( n 6 ) 阶 单圈图，则 ( 又+ e ) 0 湖南师范大学高校教师硕士论文 即w ( + e ) 0 ( 因n 6 ) ，所以w ( a ) w ( c 4 ( s n 一3 ) ) 。 当礼为奇数时，w ( a ) 一w ( q ( 晶一3 ) ) = n ( 礼2 1 ) 一( 礼2 一礼一4 ) = ( 礼3 8 n 2 + 7 n + 3 2 ) 0 ，所以w ( g ) 形( q ( 品一3 ) ) 。 ( i i ) 若后1 由推论5 知，w ( a ) w ( a 1 ) ，其中 g 1 = c 鬻札2 ，札( s t l + 1 ，s t 2 + 1 ，s t k + 1 ) ， l ：l l + f 2 + + f k = n m ，等号成立当且仅当g 笺g 1 。 又由引理6 知， w ( g 1 ) w ( c 鬻( s + 1 ) ) = w ( 嘴( & 一m + 1 ) ) 且等号成立当且仅当g 。竺嘴( s + 。) 。 所以，( g ) ( 嘴( s + 。) ) 等号成立当且仅当g 1 笺罐( s + ) ( 这 里m 3 ，因g 喾& + e ) 。 再由引理7 知， ( 嘴( 岛一m + 1 ) ) w ( c 蔫u 1 ( 一m + 2 ) ) w ( c 4 ( 一3 ) ) 因此，( g ) w ( c 4 ( s n 一3 ) ) ，等号成立当且仅当m = 4 和g 竺嘴( - r e + 1 ) ， 即g 竺a ( 岛一3 ) 。 ( i i ) 最后，当m = 3 时，我们证明：若g = 瞄1 毗m 3 ( 乃，乃，t 3 ) 喾 & + e ，则有w ( g ) w ( c 4 ( s n 一3 ) ) ，等号成立当且仅当g 竺q ( 一3 ) 或 四1 毗( 岛，一3 ) 。 因佗6 ，m = 3 ，所以l 七3 。 ( i ) k = 3 时，由推论5 知，( g ) w ( 嗜1 毗舢3 ( 。+ 1 鼠。+ 1 岛：+ 1 ) ) 等 号成立当且仅当g 型瞄1 毗一3 ( s t 。+ 1 ，s z 。十1 ，s l ：十1 ) 。 单圈图的w i e n e r 指数1 3 4 知 下面证明w ( 四1 ，讹( s l 。+ l s z 。+ 1 ，。+ 1 ) ) w ( 瞄1 m ( p 2 ，一3 ) ，由定理 w ( 四1 u 2 ( b ，。一3 ) ) = w ( c 3 ) + ( 礼一3 ) u + 2 ( n 一3 ) + ( 礼一4 ) 2 + 3 ( n 4 ) + 1 = n 2 一礼一4 = w ( q ( 品一3 ) ) 而 w ( 鳄1 地m 3 ( s 1 1 + 1 s 1 2 + 1 ，s 1 2 + 1 ) ) = w ( c a ) + ( _ n 一3 ) u + 2 ( 1 1 + 1 2 + 1 3 ) + ( f + f ；+ 2 ；) + 3 ( 1 1 1 2 + 1 1 1 3 + 1 2 1 3 ) = w ( 国) + ( 扎一3 ) u + 2 ( 扎一3 ) + ( 礼一3 ) 2 + ( 1 1 1 2 + 1 1 1 3 + 1 2 1 3 ) ( c a ) + ( 几一3 ) u + 2 ( n 一3 ) + ( 礼一3 ) 2 + ( 1 1 + 1 2 + 1 3 ) = 缈( 仍) + ( n 一3 ) u + 2 ( n 一3 ) + ( n 一3 ) 2 + ( 礼一3 ) = n 2 一n 一3 ( 嘴1 毗( b ，& 一3 ) ) ( i i ) 七= 2 时，由推论5 知，w ( g ) ( 鳄1 m ( ，+ 1 s l 。+ 1 ) ) 等号成立 当且仅当 g 鲁喏1 毗( s 2 。+ 1 ，岛2 + 1 ) 。 下面证明： 彬( 嘴1 ，价( s l 。+ l s l 。+ 1 ) ) w ( 硝1 “2 ( 马，& 一3 ) ) 。 由定理4 知， ( 鳄1 ( s z ，+ 1 岛。+ 1 ) ) w ( c 3 ) + 2 ( n 一3 ) + 2 ( 1 1 + 1 2 ) + ( 2 ；+ 2 ；+ 2 ；) + 3 1 1 1 2 3 + 4 ( n 一3 ) + ( n 一3 ) 2 + 1 1 1 2 3 + 4 ( n 一3 ) + ( n 一3 ) 2 + ( n 一4 ) n 2 n 4 且等号成立当且仅当f ，= 1 或l 。= 1 。 ( 注：上述不等式是由于f 1 + 1 2 = n 3 , 1 1 1 n 一4 ，1 1 2 礼一4 ， 所以有i i l 2 = f 1 ( 礼一3 1 1 ) n 一4 且等号成立当且仅当1 1 = 1 或2 2 = 1 。) 所以， ( 鳄1 m ( & 。+ 1 ，岛。+ 1 ) ) w ( 鳄1 m ( p 2 ，岛一3 ) ) 仅当四1 心( 岛。+ 1 岛。+ 1 ) 竺瞄1 ，札2 ( 岛，& 一3 ) 。 且等号成立当且 ( i i i ) k = 1 时，因g = 四1 ( 丑) 喾& + e ，所以噩喾晶一2 。 w ( 鳄1 ( 丑) ) = ( 仍) + ( n 一3 ) u + 2 虹( 让1 ) + ( 丑) 。 由于孔是一个n 一2 阶树，且t 1 喾s n 一2 ，所以d n ( u 1 ) n 一3 。 1 4 湖南师范大学高校教师硕士论文 v l v 2 图2 n 阶树_ 3 1 由文献【2 1 】知，吨。是所有n 阶树中具有次小w i e n e r 指数的树， 且w ( t i 一3 1 ) = ( n 一2 ) ( n + 1 ) 。所以w ( t 1 ) w ( 霹一5 ，1 ) = ( 礼一4 ) ( n 1 ) 。从而 w ( 掣，( n ) ) w ( c 3 ) + ( n 3 ) u + 2 ( n 3 ) + ( 礼一4 ) ( n 一1 ) w ( g ；1 伽( p 2 ，s n - 3 ) ) 。 由上可知，w ( g ) w ( c 4 ( s n 一3 ) ) = ( 喏1 ”( p 2 ，s n 一3 ) ) = n 2 礼一3 且 等号成立当且仅当g 兰c 4 ( s 一3 ) 或g 竺四1 2 ( p 2 ，晶一3 ) 。 因而，具有次小w i e n e r 指数的单圈图是c 4 ( s n 一。) 和鳄1 抛( p 2 ，一3 ) 。 单圈图的w i e n e r 指数 3 2 具有次大w i e n e r 指数的单圈图 这一节我们给出n ( n 5 ) 阶单圈图g = ( v e ) 的w i e n e r 指数的次 大值，并刻划出n 阶单圈图中具有次大w i e n e r 指数的图的特征。 引理1 2 ( 2 2 】) 设t 是一个与r 和t ( n 一3 ，1 ，1 ) 不同构的n 阶树， 则有 w ( t ) w ( t ( n 一3 ，l ，1 ) ) w ( r ) 其中t ( n ，忆，n m ) 表示在m + 1 阶星图+ 。的各条边上分别插入 礼l 一1 ，n 2 1 ，n m 一1 个顶点得到的一个n 阶似星图，因而，t ( n 一3 ，1 ，1 ) 是n 阶树中w i e n e r 指数次大的树。 证明：由引理2 计算得 w c t c n 一3 ，= ( n ；1 ) 一n + 3 所以w ( t ( n 一3 ，1 ，1 ) ) w ( r ) 对于任一不同构于r 的任意一个死阶树t ，至少存在一个分 枝点札，d t ( u ) = m ( m 3 ) ，t 一 札) 的仇个连通分枝t i 的阶n ( 互) = n i ， i = l ，2 ，m ，贝i j 有礼1 + 礼2 + + n m = n 一1 等号成立当且仅当，t 只有一个分枝点u ，且t 一 u ) 的m 个连通分 枝分别是长为n 1 一l ，礼2 1 ，n m 一1 的路，即t 竺t ( n l ，锄，扎m ) 下面证明w ( t ( n 一3 ，1 ，1 ) w ( t ( n 1 ，n m ) ) 且等号成立当且仅 当t ( n 一3 ，l ，1 ) ) 竺t ( n l ，n 2 ，礼m ) ( 1 ) 当m 4 时，有 w ( t ( n 一3 ，1 ，1 ) ) 一w ( t ( n l ，7 2 2 ，n m ) ) = l i f w ( t ( n l ，? 2 2 ，r i m ) ) ( 2 ) 当m = 3 时，不妨设1 2 1 n 2 n 3 1 若n 3 1 ，则有 w ( t ( n l + l ，佗2 ，礼3 1 ) ) 一w ( t ( n l ，凡2 ， = n l n 2 n 3 一( n l + 1 ) n 2 ( 1 2 3 1 ) = ( 7 2 1 + 1 ) 一n 3 1 1 2 2 0 由此可知w ( t ( n 1 ，n 2 ，礼3 ) ) w ( t ( n 1 + 1 ，礼2 ，礼3 1 ) ) - w ( t ( n 1 + n 3 1 ，? 2 2 ，1 ) ) 类似地可证，若n 3 = 1 ，n 2 1 ，有 w ( t ( n l + ? 2 3 1 ，n 2 ，1 ) ) w ( t ( n l + n 3 ，1 2 2 1 ，1 ) ) w ( t ( n l + ? 2 3 + n 2 2 ，l ，1 ) ) = w ( t ( n 一3 ，l ，1 ) ) 因此，w ( t ( n 一3 ，1 ，1 ) ) w ( t ( n l ，n 3 ) ) 且等号成立当且仅当 n 3 = 礼2 = 1 ，即t ( 1 2 3 ，1 ，1 ) ) 竺t ( 1 2 1 ，? 2 2 ，n 3 ) 综上所述，引理1 2 得证 定理1 3 设g = 础m ，m ( 孔，t 2 ，t k ) 喾c 3 ( p 钆一2 ) 是一个n ( n 6 ) 阶单圈图，则 w ( v ) ( q ( r 一3 ) ) w ( c 3 ( r 一2 ) ) 左边等号成立当且仅当g 竺q ( r 一。) 因而，具有次大w i e n e r 指数的 单圈图是c 4 ( p n s ) 一o - - * - - - - 日 图3 n 阶单圈图c 4 ( p 。一3 ) 单圈图的w i e n e r 指数 证明：( i ) 首先通过计算知 w ( c 4 ( p n 一3 ) ) = ( n 3 1 3 n + 3 6 ) ，( 国( r 一2 ) ) = ( 礼3 7 礼+ 1 2 ) 于是， ( a ( r 一3 ) ) 一彬( 岛( p 礼一2 ) ) = 丢( 一8 n + 2 4 ) o 即w ( c 4 ( p n 一3 ) ) w ( c 3 ( p 一2 ) ) ( i i ) 其次，当m 4 时，我们证明：若g = 嘴m ，m ( 孔，疋，死) ( 显 然g 喾岛( p n 一2 ) ) ，则有w ( g ) w ( c d p , 。一3 ) 且等号成立当且仅当g 笺 q ( p n 一3 ) ( i ) 若k = 0 ，则g = g ， 当n 为偶数时，w ( g ) 一w ( q ( r 一3 ) ) = 礼3 5 1 i 、n 3 1 3 n + 3 6 ) = 刍( 一礼3 + 4 2 n 一1 4 4 ) 当咒6 时，寺( 一n 3 + 4 2 n 一1 4 4 ) 0 ，即w ( g ) w ( c 4 ( p 一3 ) 当n 为奇数时，( g ) 一w ( q ( r 一3 ) ) = 礼( n 2 一1 ) 一 ( 礼3 1 3 n + 3 6 ) = 去( 一礼3 + 3 9 n 一1 4 4 ) ，当礼6 时，击( 一礼3 + 3 9 n 一1 4 4 ) 0 ，即w ( g ) w ( 嘴( r m + 1 ) ( i i i ) 最后，当m = 3 时，我们证明：若g = 掣- m ，u 。( 噩，毋，t 3 ) 喾 c 3 ( p 扎一2 ) ，则有w ( g ) w ( g ) 七= l 时，因g = 鳄1 ( 乃) 碧鳄1 ( r 一2 ) ，所以丑喾r 4 单圈图的w i e n e r 指数 1 9 w ( 瞄1 ( 丑) ) = w ( c 3 ) + ( 礼一3 ) u + 2 d n ( u 1 ) + w ( t 1 ) 由于t ( 佗一5 ，1 ，1 ) 是一个n 一2 阶树，且丑掌t 一5 ，1 ，1 ) ，所以 d 丁( n 一5 ，1 ，1 ) ( 札1 ) d n ( 让1 ) ，w ( t ( n 一5 ，1 ，1 ) ) w ( t 1 ) 得k = 1 时， w ( c ；1 ( t ( 礼一 5 ，1 ，1 ) ) ) ( 鳄1 ( 正) ) k = 2 时，由推论5 知，( g ) 彬( 四1 批( p l ，+ 1 b 。+ 1 ) ) 等号成立当 且仅当g 竺四h 毗( r 1 十1 ，日。+ 1 ) w ( 四1 毗( 蜀，+ 1 毋。+ 1 ) ) 一( 四1 ( t ( n 一5 ，1 ，1 ) ) ) = w ( c 3 ) + ( 礼一3 ) u + 2 d p z 。+ 1 ( u 1 ) + 2 d p z 2 + ，( 乱2 ) + 彤( b 1 + 1 ) + w ( 5 2 + 1 ) 一 w ( c 3 ) 十( n 一3 ) u + 2 d r ( n 一5 ，1 ，1 ) ( u 1 ) + w ( t ( n 一5 ，1 ，1 ) ) 】 = 2 d p ，+ ，( 乱1 ) + 2 d p , 2 + 。( 钍2 ) + w ( 局l + 1 ) + ( 旦。十1 ) 一2 t i t ( n 一5 ，l ，1 ) ( u l w ( t ( n 一5 ，1 ，1 ) ) = 1 1 ( 1 l + 1 ) + 1 2 ( 1 2 + 1 ) + ( f 一z i ) + ( z 一f ) 一( n 一2 ) ( n 一4 ) + ( 礼3 6 n 2 + 6 n - 4 - 2 2 ) = ( 礼一6 1 1 1 2 3 ) 而f 1 + 1 2 = n 一3 ，m i n l l l 2 l l + 1 2 = 礼一3 ，1 1 1 ，1 2 1 ) = n 一4 所以w ( 瞄1 抛( 蜀。+ 1 ) 最。+ 1 ) ) w ( 四1 啦一3 ( 翰。+ l ，蜀。+ l ，- f 2 。+ 1 ) ) ( 鳄1 啦一3 ( 局，+ 1 ，毋。+ 1 ，最。+ 1 ) ) = ( n 3 1 2 n + 2 7 一i z l 2 1 3 ) 一1 1 1 2 一l f l 3 1 1 1 3 w ( 四1 ( t ( n 一5 ，1 i 1 ) ) ) 一w ( 四1 也舢3 ( r 。+ 1 ，蜀。+ 1 ，毋。+ 1 ) ) = ( n 3 1 3 n + 3 0 ) 一 ( n 3 1 2 n + 2 7 1 1 1 2 1 3 ) 一1 1 1 2 1 2 1 3 1 1 1 3 = ( f l f 2 f 3 一n + 3 ) 十1 1 1 2 + 1 2 1 3 + 1 1 1 3 因n 一3