（运筹学与控制论专业论文）树的merrifieldsimmons指数与独立多项式.pdf

摘要 设s 是图g 的一个顶点子集，若s 中任意两个顶点g 中均不相邻， 则称s 是g 的一个独立集；空集乃是g 的一个独立集用瓯表示图g 中基数为k 的独立集数目，则o ( g ) = & ，其中1 1 为g 的顶点数盯( g ) 称为g 的m e r r i f i e l d s i m m o n s 指数或者盯指数同时，为了进一步研 究图的不同基数的独立集的分布，g u t m a n 和h a r a r y 引入了图的独立多 项式 q ( g ) i ( g ；x ) = f 鼠矿，岛= 1 k = o 本文主要研究了似星图依m e r r i f i e l d s i m m o n s 指数排序以及极图的 刻画，证明了连通图中双星图是由它的独立多项式唯一确定的，以及它 的独立多项式是单峰的，并找到了峰的位置 关键词：m e r r i f i e l d s i m m o n s 指数；独立多项式；排序；极图； 单峰性；似星图；双星图；排序 a b s t r a c t l e tg = ( v e ) b eas i m p l ea n dc o n n e c t e dg r a p h 奶t ht h ev e r t e xs e tv ( a ) a n d t h ee d g es e te ( g ) as u b s e ts vi sc a l l e dai n d e p e n d e n ts e to fgi fn ot w ov e r t i c e s o f sa r ea d j a c e n ti ng t h ee m p t ys e t 妒i sa l s oai n d e p e n d e n ts e to f g l e t 瓯b e t h en u m b e ro fi n d e p e n d e n ts e t so fgw i t hke l e m e n t s ，t h e no ( g ) = 鼠i sc a l l e d k = o t h em e r r i f i e l d - s i m m o n si n d e xo r 仃i n d e x ，w h e r eni st h en u m b e ro fv e r t i c e si ng i no r d e rg os t u d yt h ed i s t r i b u t i o no fc a r d i n a ln u m b e rw i t hr e s p e c tt oi n d e p e n d e n t s e t s ，g u t m a na n dh a r a r yi n t r o d u c e dt h ei n d e p e n d e n tp o l y n o m i a l a ( g ) ，( g ；正) = 鼠 k = o w h e r es o = 1 i nt h i st h e s i s ，w em a i n l yd i s c u s so nt h eo r d e r i n go fs t a r l i k et r e e sw i t hr e s p e c t t ot h e i rm e r r i f i e l d - s i m m o n si n d i c e s a n dp r o v et h a tt h ed o u b l es t a ri 8u n i q u e l y d e t e r m i n e db yi t si n d e p e n d e n tp o l y n o m i a la m o n ga l lc o n n e c t e dg r a p h sa n di t si n - d e p e n d e n tp o l y n o m i a li sa l s ou n i m o d a l i t ya n dl o c a t ei t sm o d e k e yw o r d s ：m e r r i f i e l d - s i m m o n si n d e x ；i n d e p e n d e n tp o l y n o m i a l ；o r d e r i n g ；u n i - m o d a l i t y ；s t a r l i k eg r a p h ；d o u b l es t a r ；e x t r e m a lg r a p h i i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的研究成果除了文中特别加以标注引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写的成果作品对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明本人完全 意识到本声明的法律后果由本人承担 学位论文作者签名：善砍参荔 知孑年石月白日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅本人授权湖南师范大学可以将学位论文的全部或部分 内容编人有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文 本学位论文属于 i 、保密口，在年解密后适用本授权书 2 、不保密口 ( 请在以上相应方框内打。 矗) 作者签名： 关乞奁磊 导师签名艮p 乙 4 1 日期：加略年6 月卜日 日期：驷彦啪，p 日 树的m e r r i f i e l d - s i m m o n s 指数与独立多项式 1 引言 图论是数学中一个重要的分支自从二十世纪三十年代以来，由于 在生产管理、交通运输、计算机和通讯网络等领域中许多离散问题的出 现，大大促进了图论的发展；特别是二十世纪七十年代以来，随着科学 技术的突飞猛进增长，使得图论不仅与数学的其它分支，如群论、矩阵 论、拓扑学、概率论、组合学等有了紧密的联系，而且在物理，化学，生 物、计算机科学、信息论、系统论、控制论等方面也有重要的应用价值 图的拓扑指数是从化合物的结构图衍生出来的不变量它不但可以 定量地描述分子的结构，而且可以分析相关分子的结构与性能之间的关 系当今组合化学的一个重要问题是寻找具有某种物理或化学性质的分 子自从引入了拓扑指数，至今已有1 2 0 多种被证实在分子的结构活性 性质相关性( q s a r q s p r ) 中非常有用，且新的指数不断的被提出 m e r r i f i e l d - s i m m o n s 指数是一个重要的拓扑指数，p r o d i n g e r 和t i c h y l 7 在1 9 8 2 年首次提出了这个指数并定义为仃指数，m e r r i f i d d 和s i m m o n s 5 】 在1 9 8 9 年首先研究了这个指数与如沸点，溶解度，密度等有机物的物理 化学性质有着密切联系，w a n g 等 1 1 】后来进一步研究了这方面性质关 于m e r r i f i e l d - s i m m o n s 指数，一个主要的研究内容是：研究一些特殊图类的 m e r r i f i e l d - s i m m o n s 指数以及刻画m e r r i f i e l d - s i m m o n s 指数极图，主要有以下 一些结果： ( 1 ) 对于树，k i r s c h e n h o f e r ，p r o d i n g e r 和t i c h y 6 】分别证明了路p n 和星 图& 分别具有最小和最大的m e r r i f i e l d - s i m m o n s 指数 ( 2 ) 对于单圈图，p e d e r s e n ，v e s t e r g a a d 1 5 】给出了m e r r i f i e l d - s i m m o n s 指 数的上界和下界 ( 3 ) 对于最大外平面图，a l a m e d d i n e 1 0 】研究了m e r r i f i e l d - s i m m o n s 指数 的界 1 硕士学位论文 ( 4 ) 对于n 阶连通图，p e d e r s e n ，v e s t e r g a a d 1 0 证明了m e r r i t i e l d - s i m m o n s 指数的界 ( 5 ) 对于至多一个圈的图，c h o u 和c h a n g 4 3 】证明了m e r r i f i e l d - s i m m o n s 指数的界 ( 6 ) 对于( n ，n + 1 ) 图，d e n g 1 6 】给出了m e r r i f i e l d s i m m o n s 指数的界以 及刻画了对应的极图 ( 7 ) m e r r i f i e l d 和s i m m o n s 5 】研究了m e r r i t i e l d - s i m m o n s 指数在化学中的 实际应用 进一步考虑图的各种基数的独立集数目及其分布，g u t m a n 和h a r a r y 引入了图的独立多项式以及图的独立多项式的性质，主要是独立多项式 系数的单峰性 关于图的独立多项式以及独立多项式的单峰性，主要有以下结果： ( 1 ) 对于良覆盖图，b r o w n ，d i l c h e r 和n o w a k o w s k i 2 6 】给出了独立多项 式零点的界( b r o w n ，d i l c h e r 和n o w a k o w s l ( i 也描述了一般图没有这样的界 存在) ( 2 ) 对于一类优覆盖图( v e r yw e l l - c o v e r e dg r a p h s ) ，l e v i t 和m a n d r e s c u 2 9 证明了其独立多项式是单峰的 ( 3 ) 对于无爪图( c l a w - f r e eg r a p h ) ，h a m i d o u n e 2 7 证明了其独立多项式是 单峰的 ( 4 ) 对于良覆盖s p i d e r 树，l e v i t 和m a n d r e s c u 2 8 】证明了其独立多项 式是单峰的 ( 5 ) l e v i t 和m a n d r e s c u 2 2 】也证明了蜈蚣树的独立多项式是单峰的 本文研究了似星图中m e r r i f i e l d - s i m m o n s 指数和双星图的独立多项式， 得到了以下结果： 2 树的m e r r i f i e l d s i m m o n s 指数与独立多项式 ( i ) 对具有不同分枝的似星图的m e r r i f i e l d - s i m m o n s 指数进行了比较； 对具有相同分枝的似星树的m e r r i f i e l d - s i m m o n s 指数进行了排序；并刻画 了似星树关于m e r r i f i e l d - s i m m o n s 指数的极图 ( i i ) 证明了在树中双星图是由它的独立多项式唯一决定 ( t 扰) 证明了双星图( 非良覆盖的) 独立多项式是单峰的，并且找到了 峰的位置 ， 3 树的m e r r i f i e l d s i m m o n s 指数与独立多项式 2 似星图依m e r r i f i e l d s i m m o n s 指数排序 本章对具有不同分枝的似星树的m e r r i f i e l d - s i m m o n s 指数进行了比较， 对具有相同分枝的似星树的m e r r i f i e l d s i m m o n s 指数进行了排序；以及利 用誓 i ( b 一2t j 己一1u 彤) ( y = 1 ) ， 或者i ( b 一2ut ( y 一2 ，) l ( b 一2u 己一1u 爿) ( y 2 ) 所以，i ( t ( x ，y ，6 ) ) i ( t ( x + y b ) ) 证毕 7 硕士学位论文 具有相同分枝的似星树的m e r r i f i e l d s i m m o n s 指数的比较 引理2 2 2 设z 和y 是正整数，满足1 z y 一2 ，且只，b 和g 互 不相交，则对任意图g 有 i ( bub ug ) 一z ( 只+ lub 一1ug ) = ( 一1 ) z k ( 己- - z - - 2ug ) 一t ( 马- - z - - 1ug ) 】 证明利用引理2 2 1 ( i ) ，有 t ( 足ub ug ) = i ( bub 一1ug ) + i ( 只u b 一2ug ) ， i ( 只+ lub 一1ug ) = i ( bub 一1ug ) + i ( 只一1ub 一1ug ) ， t ( 只u 己u g ) 一i ( 只+ lu b 一1u g ) = 一_ ( 只一1ub 一1ug ) 一i ( 只ub 一2ug ) 】 = ( - 1 ) 2 【i ( 足一2ub 一2ug ) 一i ( 只一1u 已一3ug ) 】 = = ( - 1 ) z k ( 己一ug ) 一 ( p lu 马- - x - - 1u g ) = ( - a ) 2 p ( 与一2ug ) 一2 i ( b - - z - - 1ug ) 】 = ( - 1 ) 1 i ( b - z - - 2 1 9g ) 一z ( b - - z - - 1ug ) 】 所以，引理2 2 2 成立，证毕 下面比较具有相同分枝的似星树的m e r r i f i e l d - s i m m o n s 指数 对于固定的正整数凡和d ，t ( x ，6 ) s ( 佗，d ) 利用引理2 2 1 ( i i ) ，有 i ( t ( x ，y ，6 ) ) = i ( 只ut ( y ，6 ) ) 一i ( 只一2u 弓一1ur ”) = i ( 只ub ur ) 一t ( 只ub 一2ur ”) 一i ( r 一2ub 一1ur ”) i ( t ( x + 1 ，掣一1 ，6 ) ) = i ( 只+ 1ut ( y 一1 ，6 ) ) 一i ( 己一1u 己一2ur ”) = i ( b + 1u 已一1ur ) 一i ( 兄+ 1u 已一3u 尉) 一t ( b 一1ub 一2u 尉) 令a l = i ( t ( x ，y ，6 ) ) 一i ( t ( x + 1 ，y 一1 ，6 ) ) ，则 8 树的m e r r i f i e l d - s i m m o n s 指数与独立多项式 a1=l ( 只ue u 冗) 一l ( 只u 冗一2u 彤) 一t ( b 一2u 己一lur ，) 】 一一( 只+ lub lur ) 一i ( 忍+ 1ub 一3u 爿) 一t ( b lub 一2u 硝，) 】 ( - 1 ) 士弘( b - - x - - 2ur ) 一i ( b - - x - - 1ur ) 】 - ( - 1 ) 王【i ( 己一霉一4ur ”) 一i ( 己- - x - - 3ur ) 】 一( 一1 ) 霉一2 p ( b - - x - - | ur ”) 一i ( 马一害ur ”) 】( 由弓i 理2 2 2 ) ( - 1 ) 善【i ( 己- - x - - 2ur ) + i ( 马- - x - - 3u 尉) + t ( 己一王ur ”) 一i ( 局- - x - - 1ur ) 一t ( b 一王一4u 彤) 一t ( b 一2 一lu 尉) 】 ( - 1 ) 计1 p ( b - - x - - 3ur ) + i ( b 一扣4u 彤) + i ( 马一卫一lu 爿) 一t ( b - - x - - 3u 彤) 一t ( 己一zu 爿) 】 ( - 1 ) 外1k ( 弓- - x - - 3u 剧) + t ( b - - x - - 3t i ) + i ( b 一一4u 彤) + i ( b - - x - - lur ”) 一i ( b - - x - - 3u 彤) 一t ( b 一零一lu 硝) 一t ( b - - z - - 2ur ”) 】( 由引理2 2 1 ( i ) ) ( - 1 ) 计1 瞄( 马- - x - - 3u 影) 一t ( b - - x - - 3u 彤) 】 于是， i ( p y z 一3ur ) i ( 己一一3ur ”) 所以， - 耋缀釜 因此，我们得到如下定理： 定理2 2 2 设x + y = 名和吲= 矿，则s ( n ，回中的似星树满足下面关系 ( i ) 当矿是奇数时，t ( 1 ，z 一1 ，6 ) 卜t ( 2 ，z 一2 ，b ) _ ，t ( 3 ，z 一3 ，6 ) t ( 5 ，名一5 ，6 ) 卜t ( k ，名一七 6 ) 1 0 i ( g ，- - z - - 3u r ”) 】 树的m e r r i f i e l d s i m m o n s 指数与独立多项式 其中当矿是奇数时，k = z ；当矿和z 都是偶数时，k = 矿一1 ；当矿是 偶数且名是奇数时，k = z + 1 ； ( i i ) t ( 2 ，z 一2 ，b ) t ( 4 ，z 一4 ，6 ) t ( 6 ，z 一6 ，b ) - t t ( 2 ，2 ，2 ，1 ，1 ，1 ) ； ( i i ) 若n 2 d + 1 ，则对于任意t s ( 佗，d ) 一 t ( 1 ，1 ，1 ，n d 一 1 ) ，t ( 2 ，2 ，2 ，n 一2 d 一1 ) ，有 t ( 1 ，1 ，1 ，n d 一1 ) 卜t - t ( 2 ，2 ，2 ，n 一2 d 一1 ) 推论2 2 2 若t s ( n ) ，死6 ，贝l j t ( 1 ，1 ，1 ) - t - t ( 2 ，2 ，n 一5 ) 树的m e r r i f i e l d - s i m m o n s 指数与独立多项式 双星图的独立多项式 本章证明了在连通图中双星图由它的独立多项式唯一决定的，即若 一个连通图与双星图有相同的独立多项式，则这图一定是双星图；还证 明了双星图( 非良覆盖的) 独立多项式是单峰的，并且找到了峰的位置 3 1 基本概念 & ，是星图，连接& ，岛的中心得到的树称为双星图，记为阳 如图3 1 1 图3 1 1 双星图朋 卜 设g = ( v ，e ) 是简单图，scv ( a ) 是g 的一个独立集；若任取u v ( c ) 一只su 让 不是独立集，则称s 是g 的一个极大独立集；若g 中 已无独立集s 7 ，使得l s l i s l ，则称s 是g 的一个最大独立集；此时，记 q ( g ) = l s l ，q ( g ) 叫做g 的独立数以后我们用鼠表示g 中基数为k 的 独立集的数目，称多项式： n ( g ) 鼠矿，s o = 1 k = 0 是g 的独立多项式，记作i i g ；x ) 或，( g ) 】3 硕士学位论文 图3 1 2 所示的图的独立多项式是： 1 + 6 x + 5 x 2 叭 图3 1 2 对于图g ，若g 中的所有的极大独立集有相同的基数，则称g 是良 覆盖的( w e l l - c o v e r e d ) 设 y ( g ) ，g 中与v 关联的数目称为v 的度，记 作d e g c ( v ) 或简记作d e g ( v ) d e g ( v ) = 0 和1 的点分别称为g 的孤立点和端 点在一个图g 中，若对所有的秽1 厂( g ) ，均有d e g ( v ) = r ，则这样的图称 为是r 度正则的m 个点的m - 1 度正则的图中任何两点均邻接，称为完 全图，记作 对于非负序列a o ，a 。，如果存在非负数k 使得a o a l 口七一。a 七a 七+ 。2 a n ，则称此序列是单峰的，其中k 称为峰的位置或 指标；特别的a 詹一1 a 七+ 1 称峰是唯一的 例3 1 1 二项式系数序列是单峰的 当n = 2 m 时， ( ：) ( m 二1 ) ( 三) ( m ：。) 主( ：) ； 当n = 2 m + l 时， 1 4 ( ：) ( m 1 二1 ) ( 二) = ( m ：i ) ( m 二1 ) ( ：) 一个多项式妻a k x k 是单峰的，如果其系数n o ，口t ，口，l 是一个单峰的 k - - - - o n 序列序列n o ，。a n 的峰位置也称作这个多项式邑鲰矿的峰位置 1 5 树的m e r r i f i e l d - s i m m o n s 指数与独立多项式 3 2 双星图由独立多项式唯一决定 在计算各类图的独立多项式时，下面的结论是非常有用的工具设 g l ，g 2 是两个简单图，g 是g 1 ，g 2 的不相交并，其中g 的顶点是v ( c - ) 与 v ( g 2 ) 的不相交并，边集也是e ( g t ) 与e ( g 2 ) 的不相交并，记作g = g 。u g 2 我们有x ( c 1ug 2 ，z ) = ，( g 1 ，z ) i ( a 2 ，z ) 以及有下面引理 引理3 2 1 ( f 2 0 ) 设g = ( ve ) ，v , u v e 和ucv 使得g m 是完 全子图，则下列等式成立 ( i ) i ( g ；x ) = i ( g t t ，；z ) + x x ( g 一如1 ；z ) ； ( i i ) i ( g ；z ) = i ( a u ；z ) + z b u z ( g n n ；z ) ； ( i i i ) i ( g ；x ) = z ( c u v ；z ) 一x 2 i ( g 一( g u 】u ( 口) ) ；z ) 显然对于任何两个同构图，其独立多项式相同；反之，不一定成立， 即具有相同独立多项式的两个图并一定同构例如图3 2 3 ： 图3 2 3 下面证明在连通图中双星图是由它的独立多项式唯一决定的 定理3 2 1 在连通图中双星图是由它的独立多项式唯一决定的 1 7 硕士学位论文 证明i n 条悬挂点与秒相连，1 1 条悬挂边与吨相连，v l 0 2 e ( g ) ，记 双星图g 为岛朋从t 2 的n 条悬挂边删去i 条边0 佗) ，增加i 条边与秽。 相连，得“n - i 如图3 2 4 m 乱仇+ i 图3 2 4 情形1 不同构的双星图，其独立多项式不相同 根据引理3 2 1 ， j ( 岛，n ；z ) = ( 1 + z ) “，( s k ；z ) + z ( 1 + z ) n = ( 1 + z ) ”【( 1 + z ) n + 。】- t - x ( 1 - i - z ) n = ( 1 - t - z ) m + n + z ( 1 + z ) 仇+ z ( 1 + z ) ”； j ( s 矗+ ，。一；z ) = ( 1 + z ) m “j ( 一t ；z ) + z ( 1 + z ) n 一 = ( 1 + z ) ”“【( 1 + z ) ”一+ x 】+ z ( 1 + z ) n 一 = ( i + z ) ”+ n + x ( 1 + z ) ”“+ x ( 1 - t - z ) n 一； 则j ( ，n ；z ) 一j ( s m 州，n i ；z ) = ( 1 + z ) m 【1 一( 1 + z ) 】+ z ( 1 + z ) “一【( 1 + 。) 一1 】 = 【1 一( 1 - i - z ) 】p ( 1 + z ) m z ( 1 + z ) n 一1 = z 【1 一( 1 + z ) 】【( 1 - i - m ) m 一( 1 + z ) ”_ 】 因为1 一( 1 + z ) 0 ，所以 ，( ，n ；z ) = ，( s n + i ，n i ；。) 车 m = n t 即，n 和“n t 是同一个双星图 1 8 树的m e r r i f i e l d s i m m o n s 指数与独立多项式 - - _ l - _ _ _ _ i 1 | l i i _ l i _ _ _ _ i l _ l - _ _ l l l - 。_ - 。_ _ - l _ _ _ _ _ _ - l - - l _ 故在双星图中，独立多项式唯一决定双星图 情形2 进一步证明，双星图在树中唯一由独立多项式决定 在树g 中，设i v ( g ) i = m + 佗+ 2 ，g 的独立多项式为 i ( g ；x ) = 1 + s i x + 岛z 2 + + + n 矿+ n 假设树g 与。有相同的独立多项式，根据岛，。的独立多项式系数 特点： i + n = 1 ，f h + 。+ l = 0 ，k + n + 2 = 0 图g 中的点之间的邻接关系只可能为g - 或g 2 ，如图3 2 5 m + n ，- 一， 。 x y x g l g 2 图3 2 5 y ( i ) x y e ( g ) ，m + n 个孤立顶点只能与x ，y 中一个顶点相连( 如果某个 顶点同时与x y 相连与图g 是矛盾的) 显然对应图为双星图如上图g 所 示 ( i i ) x y e ( g ) ，只有一个顶点同时与x ，y 相连，其余m + n + 1 个顶点只 能与x ，y 中一个顶点相连，如图g 。所示因此，在树中与双星图可能具 有相同独立多项式的只能是g z 1 9 硕士学位论文 下面证明双星图g 。与g 。的独立多项式不相等 设双星图g 。中有m 个顶点与x 相连，n 个顶点与y 相连，记为 则如n 与g z 如下图3 2 6 所示： 佗 k 图3 2 6 其中k + l + l = m + n 不妨设m n ，k f ， 设。的独立多项式： p ( x ) = 1 + a l z + a 2 x 2 + + a m + n z ”+ n = ( 1 + z ) m + n + z ( 1 + z ) m + z ( 1 + z ) ”； 图g 2 的独立多项式： g ) = l + b l x + b 2 x 2 + + b m + n z m 押= ( 1 + z ) 七+ 件1 + z ( 1 + z ) 七+ z ( 1 + z ) + z 2 下面分两种情况进行讨论， ( i ) 当k = l 时，k 、l 、1 2 1 、n 存在下面两种关系： ( i ) k = 2 = m n ，( i i ) m k = z n ， 此时，+ - = ( m n + + l 竹) + ( ：) ，k + t = ( 七：二 1 ) ， 所以，n n + l k + l ( i i ) 当k z 时，k 、1 、m 、1 1 存在下面六种关系： ( i ) k m 礼 z ；( i i ) k = m z 弼( i i i ) k m = n z 树的m e r r i f i e l d - s i m m o n s 指数与独立多项式 此时，口- = ( 了：- ) ，饥+ t = ( 七二：1 ) + ( ：) 所以，口l + 1 6 l + l ； ( i v ) k 仇 n = z ；( v i ) 七 仇= n = z 此时， n 七+ 。= ( 了：? ) ( ：) + ( ：) ，k + - = ( m k + + l n ) + ( ：) + ( ：) 所以，a 七+ l b k + l ； ( v ) m k z 3 , b l n 【宁卜1 成立 当七6 时，上式进一步可以化为2 堡軎翌冬笔攒一2 七2 + 4 七 2 k + z 3 k + 3 4 k + 4 5 k + 5 6 2 k 2 + 4 k 2 鲁+ 百k 2 + 而k 2 + 西k 2 + 等+ 葡k 2 】一2 七：+ 4 七 = 2 兰一七2 + 4 七 o 当m 是奇数时，类似可以证得口【宰一1 l o 【华】+ 1 ( 3 ) 当n 2 ，m 2 时，分七种情况进行讨论 ( i ) 当n = m 时， 忤一= + n ) + ( 一n ) ， 。一- = ) + ( 扎二2 ) + ( n 二2 ) ， 。嗍= ) + ( 显然，a 2 - t - 1 n 【字】+ 1 - 当n = 2 、3 、4 、5 时代入可以验证a ：- t - 1 a - 。- = t - ! 一1 成立 靴6 叭喇1 料。= 燕一舻+ 3 n - - - - - 掣学掣 彳地 4 口鼍并拙 。 所以 a 。 n + 2 m 一1 1 o 【半】+ 1 f i i l 当n ：m 一1 时 。嘲一= 1 ) + ( n 二1 ) + ( n 二1 ) ， 。嘲r = 2 n + 1 ) + ( 删n ) + ( ：二 口嘲+ 1 = = 2 n + 1 ) + + 1 ) 显然o 【半】 口【字1 + 1 当n = 2 、3 、4 、5 时代入可以验证o 【字】 口【字卜1 成立 当喇时字一嘲- 1 - 筹销+ 2 n 一踹2 棚 ：筹篇一矿+ n = 2 字孚莩一舻+ 几 o 所j 以， o 【生产一1 】【旦笋】夕u 【生产1 + 1 ( i i i ) 当n = m 一2 时， 口嘲扩2 n + 2 ) + + 2 ) ， 口。- _ _ 铲2 m _ _ l - - a n - - - - ( 2 n ，2 ) + ( n 二1 ) + ( ：；) ， 口t 字m = 扩2 n n + + 2 2 ) + n n + + 2 1 ) 显然，o 【字】 n 【半” 当n = 2 、3 、4 、5 时，代入可以验证a - - - f - 严 q 半卜1 成立 当喇时 0 嘲1 料。= 踹一黼小觜 一丛孥业 鲁揣一百n 3 = 字字半一岛6 o 哪一可一 万砸丽一百2t 丁1 一 硕士学位论文 ( i v ) 当r , = m 一3 时， 口嘲= 帅= 2 n + 3 ) + + 3 ) ， 口【警卜1 o 【字】+ 1 ( 2 = 3 ) + ( 佗二。) + ( ， = + 2 = 2 n + 3 ) + ( n n + + 3 1 ) 显然，口【宁】 口【卫铲】+ 1 当n = 2 、3 、4 、5 时，代入可以验证o 【半j o 【字卜l 成立 当n 6 时，。 - 。- - + y - 川嘲1 - 踹+ 1 + 丛冬举型 一f ! 兰! ! ! 一n 一( ! 1 21 1 ! ! f 兰! ! 堡、! ( ! ! 兰! ! 一n 4 + 2 n s 一 ( n + 3 ) ! n ! ” 41 7 ( n + 3 ) ! ( 孔+ 可一矿一 型鹗篇篇型 o 所以，口【半一1 】 o 【字】+ 1 ( v ) 当佗= m 一4 时， 。嘲= 帅= 2 n + 4 ) + 4 ) 哗h = 帅= 2 n + 4 ) + + 4 ) ， 。嘲圹咖= 2 n + 4 ) + ( 篇) 显然，a - 。- - f - 1 口【字】+ 1 当n = 2 、3 、4 、5 时，代入可以验证n 【字】 o 【宁卜l 成立 当n 6 时柚字一嗍。1 。两( 2 而n + 4 而) 1 + 丛芈型 树的m e r r i f i e l d s i m m o n s 指数与独立多项式 _ - _ - _ _ - _ - _ _ - _ - l - _ _ l - _ _ - 一i t|i - 一( 2 n + 4 ) ! ( 凡+ 4 ) ( n + 3 ) ( 他+ 2 ) 礼 ，、 ( 2 n + 4 ) ! n 4 + 5 n a ( n + 3 ) ! ( n + 1 ) 1 4 1 7 ( n + 3 ) ! ( n + 2 ) 1 2 4 ( n 6 ) 簧鬟2 - - 4 一可n 4 + 5 n 3 。 所以，n 【串一l 】 q 芈| + 1 哗，= 帅= 2 n + 4 ) + n + 4 t ) ， n 嘲r 帅= 2 n + 4 ) + + 4 ) ， 件m = 帅_ ( 葛) + ( ：a 显然，q 字】 口【宁1 + 1 当n = 2 、3 。4 5 时，代入可以验证口旦# 1 n 业1 一】成立 当n 6 时一半严嗍f 蒜赫+ ( 佗+ 5 ) ( n + 4 ) ( n + 3 ) ( 佗+ 2 ) 4 1 ( 2 n + 5 ) ! ，( 佗+ 5 ) ( 佗+ 4 ) ( n + 3 ) ( n + 2 ) n 2 ( 2 n + 5 ) ! 札5 + 9 n 4 ( n + 4 ) ! ( n + 1 ) ! 5 1 7 ( n + 4 ) ! ( n + 1 ) ! 一51 一 c n 猢 畿等2 瞄一竽鹗等一掣 o 所以，n 【字一l 】 a - - t - 产 + 1 ( v i i ) 当礼m 一6 时， 口俐= ( 篱) + ( 。茹二1 ) ， 。t - 。- t - + x = ( 【茹：1 ) + ( 篙) ， 口喇f ( 。翁二1 ) + ( 。茹二1 ) ， 硕士学位论文 。嘲旷( 。茹：2 ) + ( 【茹：。) 所以，o 字】一l q 宁】+ 2 综上各种情况双星图独立多项式的峰在 字】+ 1 项 树的m e r r i f i e l d s i m m o n s 指数与独立多项式 结语 由于图的m e r r i i i e l d - s i m m o n s 指数具有广泛的实际应用，所以关于图的 m e r r i f i e l d - s i m m o n s 指数是新近研究得比较多的拓扑指数之一目前，一些 基本的简单图，如树、单圈图、双圈图以及( n ，m ) 一图的m e r r i f i e l d - s i m m o n s 指数，都得到了很好的研究本文利用图的独立集的算法的递推公式对 具有不同分支的似星图进行了排序，并对具有相同分支的似星图进行排 序以及刻画了极图本文的一个重要结论是具有相同分支的似星树当顶 点从一棵似星树的较长分支移动到较短分支上时，m e r r i f i e l d - s i m m o n s 指 数交替地增大和减小要得到单调的增加或者减少，就必须从一个分支 同时移动两个顶点到另外分支 图的独立多项式的研究也得到了很好的结果，证明了一些图( 良覆盖 s p i d e r 树，无爪图，蜈蚣树等) 的独立多项式是单峰的本文证明了双星 图( 非良覆盖的) 的独立多项式的是单峰的，而且找到了峰的位置 3 1 参考文献 【1 】i g u t m a n ，p a r t i a lo ff o r e s t sa c c o r d i n gt ot h e i rc h a r a c t e r i s t i cp o l y n o m i a l s ，i nc o r n - b i n a t o r i c s m 】，( e d i t e db ya h a j n a la n dv t s 6 s ) ，n o r t h - h o u a n d ，a m s t e r d a m ， ( 1 9 7 8 ) ，4 2 9 - 4 3 6 i2 】i g u t m a n ，f z h a n g ，o nt h eo r d i n go fg r a p h sw i t hr e s p e c tt ot h e i rm a t c h i n gn u m - b e r s j ，d i s c r e t ea p p l m a t h ，1 5 ( 1 9 8 6 ) ，2 5 - 3 3 3 】i g u t m a n ，o a r a n j o ，j r a d a ，m a t c h i n gi ns t a r l i k et r e e s j ，a p p l i e dm a t h l e t t e r s ， 1 4 ( 2 0 0 1 ) ，8 4 3 - 8 4 8 【41r e m e r r i f i e l d ，h e s i m m o n s ，t h es t r u c t u r eo fm o l e c u l a rt o p o l o g i c a ls p a c e s i j l ， t h e o r c h i m a c t a ，5 5 ( 1 9 8 0 ) ，5 5 - 7 5 f5 】r e