（基础数学专业论文）单圈图依hosoya指数与merrifieldsimmons指数的排序.pdf

单圈图依h o s o y a 指数与m e r r i f i e l d - s i m m o 璐指数的排序 中文摘要 设g = ( k e ) 是一个简单连通图，y ( g ) 和e ( g ) 分别为g 的顶点集和 边集1 y ( g ) l = 礼，i e ( g ) i = 仇分别表示g 的顶点数与边数单圈图是顶点 数与边数相等的连通图 用仇( g ，七) 表示g 的七一匹配数，则g 的h o s o y a 指数定义为名( g ) = m ( g ，克) 七= 0 s y 是图g 的一个顶点子集若在s 中的任意两个顶点都不相邻， 则称s 为g 的一个独立集图g 的m e r r i f i e l d - s i m m o n 8 指数定义为图g 的 独立集的数目 h o s o y a 指数与m e r r i 丘e l d s i m m o 璐指数是化学图论中两个重要的拓扑 指数，它们在化学中有广泛应用，在数学上也是被广泛研究 本文将通过几个图的变换研究单圈图的h o s o y a 指数与m e r r i f i e l d - s i m m o n s 指数，得到h o s o y a 指数前八小的单圈图，以及h o s o y a 指数次大的单圈图； m e r r i f i e l d - s i m m o n s 指数前七大的单圈图 关键词：h o s o y a 指数；m e r r i f i e i d s i m m o n s 指数；匹配；独立集；单圈图 高校教师在职硕士学位论文 a bs t r a c t l e tg = ( v e ) b e as i m p l ea n dc o n n e c t e dg r a p hw i t ht h ev e r t e xs e ty ( g ) a n d t h ee d g es e te ( g ) ，l y ( g ) i = i e ( g ) i = mb et h en u m b e ro fv e r t e xa n d e d g eo f g ，r e s p e c t i v e l y t h eu n i c y c l i cf a p hi sac o n n e c t e dg r a p hw h i c ht h ev e r t e xn u m b e r i se q u a lt ot h ee d g en u m b e r l e t 仇( g ，忌) b et h e 七一m a t c h i n go fg r 印hg t h e nt h eh o s o y ai n d e xo fgi s d e f i n e d 船z ( g ) = m ( g ，七) 七= 0 l e tsb eas u b s e to f t h ev e r t e xs e to fg i fa n y 乞w ov e r t i e si ns 盯en o t 删a c e n t ， t h e nsi sa ni n d e p e n d e n tv e r t e x 既to fg l e ti ( g ) d e n o t et h em e r r i f i e l d - s i m m o n s i n d e xo ft h eg r a p hg t h e ni ( g ) i st h en u i n b e ro ft h ei n d e p e n d e n tv e r t e xs e to fg h o s o y ai n d e ) ( a n dm e r r i 6 e l d s i m m o n sa r et h em o s t 丽d e l yu s e dt o p o l o g i c a l i n d i c e so fc h e i i l i c mg r a p ht h e o 够t h e yh a v eal o to fa p p l i c a t i o 璐i nc h e m i s t r y a 1 1 d h a v eb e e nw i d e l yi 玳伧s t i g a t e di nm a t h e m a t i c sa sw e l l w bs h a l li n v e s t i g a t et h eh o s o y ai n d e xa n dm e r r i f i e l d - s i m m o i l si n d e xo fu n i c y c l i c g r a p h sb ys o m ef 印ht r a n s f o r m a t i o n s ，a i l dg e tt h e 丘r s te i g h t hs m a l l e s tu n i c y c l i c g r a p h s ，a n dt h es e c o n dl a r g e s tu n i c y e l i cg r a p h sw i t hr e s p e c tt ot h eh o s o y ai n d e x ， t h e 丘r s ts e v e n t hl a r g e s tu n i c y c l i cg r 印h sw i t hr e s p e c tt om e r r i f i e l d s i m m o n si n d e x i nt h i sp a p e r k e yw o r d s ：h o s r ai n d e ) 【；m e r r i f i e l d - s i m m o n s ；m a t c h i n g ；i n d e p e n d e n ts e t ； u n i c y c l i cg r a p h i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果除文中已经注明引用的内容外，本论文不含任 何其他个人或集体已经发表或撰写过的作品成果对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明本人完全意识到本声 明的法律结果由本人承担 学位论文作者签名： 日期：d g 年f 猬8 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留，使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅本 人授权湖南师范大学可以将学位论文的全部或部分内容编人有关数据库进行检索， 可以采用影印，缩印或扫描等复制手段保存和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密日 ( 请在以上相应方框内打“ ”) 作者签名：玄b 卅寻 导师签名。即没玉 日期：“乎年l 明8 日 日期：暑年，1 月，日 单圈图依h o s o y a 指数与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 ) 中非常有用，且新的指数不断的被提出其中一 些拓扑指数是基于图中顶点的度，边与边之间的连接情况的在所有的图 的拓扑指数的研究中，h o s o y a 指数与m e r r i l i e l d s i m m o n s 指数是具有重要代 表意义的 图g 的匹配是指g 中的边子集m ，在m 中的边是不相邻的，图g 的 一个舡匹配s ，是指在g 中含有尼条边的匹配z ( g ) 表示图g 的h o s o y a 指数，h o s o y a 指数是指图g 的所有匹配的个数和【3 】，即 里 z ( g ) = m ( g ，七) 七= 0 其中是指的整数部分，仇( g ，七) 表示g 中七匹配数很显然m ( g ，o ) = 1 ，m ( g ，1 ) = m ，由h o s o y a 指数的定义我们可知当尼 时，m ( g ，七) = o 对于图g 的顶点集的一个子集，ssy ，若在s 中的任意两顶点之间 都不相邻，则称s 为g 的一个独立集g 的独立集之集记为，( g ) ，空集是 一个独立集l ( g ) 表示g 中包含顶点z 的独立集之集，l z ( g ) 表示g 中 不包含顶点z 的独立集之集g 的独立集的数目记为i ( g ) ，在理论化学上 i ( g ) 称为图g 的m e r r i l i e l d s i m m o n s 指数或伊指数【2 ，3 】 h o s o 归指数与分子的总丌一电子能f 6 】，沸点【7 】等有密切的关系已经 有很多的关于图的h o s o y a 指数的研究，文献【8 】分别刻画了具有最小，次 小h o s o y a 指数的无圈图，【9 】得到了h o s o y a 指数最小和次小的单圈图，并 且刻画了相应的极图g u t m a n 在1 1 0 证明了六角链中，线性链是唯一的具 1 高校教师在职硕士学位论文 有最小h o s o y a 指数的六角链邓与陈在【1 1 】中得到具有极值h o s o y a 指数 的单圈图邓在( 1 2 】得到具有最小h o s o y a 指数的双圈图 m e r r i f i e l d s i m m o n s 指数也是一个被研究得比较多的指数，它的数学方 面特别研究得比较透彻 4 6 】，但它在q s a r 与q s p r 方面的应用还是比 较少的在【2 】中作者证明了m e r r i 6 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 指数已经被研究了，p r o d i n g e r 与t i c h y 在【4 】 中确定在几个顶点的树里面，星图& 与路r 分别具有最大及最小的 m e r r i f i e l d - s i m m o 璐指数在【1 3 】中p e d e r s e n 与v 商t e r g a a r d 研究了树与单 圈图的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 指数的极 图邓与陈在 1 1 】中得到具有极值m e r r i f i e l d - s i m m o n 8 指数的单圈图在【1 4 】 中邓与陈得到具有最大m e r r i f i i e l d - s i m m o n s 指数的双圈图其他有关这两个 指数的研究可参考【1 5 _ 3 7 】 本文将通过几个图的基本变换研究单圈图的h o s o y a 指数与m e r r i f i e l d - s i m m o n s 指数，得到h o s o y a 指数前八小的单圈图，以及h o s o y a 指数最大，次 大的单圈图；m e r r i f i e l d s i m m o n s 指数前七大的单圈图 2 一 单圈图依h o s o y a 指数与m e r r i f i e l d - s i m m o n s 指数的排序 基本概念和基本术语 g = ( ve ) 表示顶点集为y ，边集为e 的简单连通图，n = m ，m = 吲 分别表示它的顶点数与边数g ( z ) 表示顶点z 的邻域，d g ( z ) 表示顶点。 的度，简记为也或d ( $ ) ，且d ( z ) = i g ( z ) i 度数为1 的顶点称为叶，与一个 叶子邻接的顶点称为茎，茎与它叶子所连的边称为悬挂边 f i b o n a c c i 数【2 】：o ，1 ，1 ，2 ，3 ，5 ，8 ，1 3 ，定义为f ( o ) = o ，f ( 1 ) = 1 ，且n 2 时，f ( n ) = f ( 仃一2 ) + f ( n 1 ) d ( z ，秒) 表示顶点z ，矽之间的距离始( z ，s ) 表示点z 到顶点集合s 的距离，即m i 娶d ( z ，矽) 图g 的围长是指g 中最短圈的长度，若g 中没 有圈，则定义g 的围长为无穷大( t ， ) 表示以口为根的树t 设g 竺 u ( ( 乃，口1 ) ，( 正，也) ，( 死，仇) ) 表示圈为伉= 口1 忱讥u 。，且g e ( g ) 的分 支正以让为根，1 i 七设也= ( 正) = ( 正，仇) = m a x d ( 仇，z ) i z y ( 五) ) 表示树五的树高， = m a x 鬼1 1 i 七) 简言之，以纱( ( 丑) ，( 疋) ，( 死) ) 表示u ( ( 乃， 1 ) ，( 乃，口2 ) ，( 死，魄) ) 单圈图g 是指顶点数与边数相等的连通图 表示仃个顶点的单圈图之集 钾表示n 个顶点，围长为9 的单圈图的集合 g 黜表示在围长为9 的单圈图的圈q 的一点上连接n 一9 片叶子爿料 表示在围长为9 的单圈图的圈g 的一点上连接一条长为礼一夕的路当 g 4 时，图g 珏表示在围长为9 的单圈图的圈g 上一点u 上连接n 一9 1 片叶子以及在叫( 伽q ，d ( 伽，口) = 2 ) 上连接一条边；当夕= 3 时，图g 黎 表示在图g = 伤的两个不同顶点u 和叫上分别连接n 一4 和1 条边设 昂，。，( p ，q ，7 o0 + g + r = n 一3 ) 表示将甄一，k l ，。，k 1 ，分别粘在凸的三个 顶点所得到的图它们分别如图1 所示 r ，g 和晶分别表示n 个顶点的路，圈以及星图文中有关的图论术 语请参考【1 ，3 8 】本文所讨论的图都是简单连通图 3 一 高校教师在职硕士学位论文 联卜 g 爨 g 捃 k 一4 j p 一4 一 r g 器 1 n 一9 1 j 单圈图依h o s o y a 指数与m e r r i f i e l d - s i m m o n s 指数的排序 1 2 基本引理 若e 7 e ( g ) ，我们以g 一表示g 删除f 后得到的子图同样若 w y ( g ) ，g w 表示g 去掉以及与它们相关联的边后得到的图若 w = 钞) 和f = z 秒) ，记g u 和g 一铆分别代替g 一 移) 与g 一 剐 ，g 由t 个分支g - ，g ：，g 。组成，则g 可以表示成u 名lg 下面介绍几个基本的引理 引理1 ( 【5 】) ( i ) 若图g 是由七个分支g 1 ，g 2 ，g 3 ，g ( 七1 ) 组成的， 则z ( g ) = 兀z ( g t ) t = 1 ( i i ) 若e = u 秒是g 的一条边，则z ( g ) = z ( g 一 e ) ) + z ( g 一 u ，u ) ) ( i i i ) 若u 是图g 的一个顶点，则z ( g ) = z ( g 一 u ) ) + z ( g 一 秒，z ) ) z b ( v ) 引理2 ( 【1 1 】) ( i ) 若图g 是由七个分支g ，g 2 ，g 3 ，g k ( 七1 ) 组成 的，则i ( g ) = 兀i ( g ) i = 1 ( i i ) t ( g ) = l j 一。( g ) l + l l ( g ) i = i ( g 一 z ) ) + i ( g 一陋】) ( i i i ) 若在图g 中顶点z 与! ，不相邻，则 i ( g ) = i ( g 一 z ，! ) ) + t ( g 一 zu g 函】) ) + i ( g 一 暑u 0 【叫) ) + i ( g 一 g h u g m ) ) ，其中g 【z 】= g ( z ) u z 表示g 中顶点z 的闭邻域 引理3 ( 【4 ，1 1 】) ( i ) 石( 叉) = n ，z ( g ) = f ( n 一1 ) + f ( n + 1 ) ， z ( r ) = 0 ，z ( 最) = 1 ，当礼2 时z ( r ) = f ( n + 1 ) ( i i ) i ( & ) = 2 n 一1 + 1 ，i ( r ) = f ( 住+ 2 ) ， 当n 3 时i ( g ) = f ( n 一1 ) + f ( 仡十1 ) ( i i i ) 对任意n 个顶点的树? ，f ( n + 2 ) i ( t ) 2 n 一1 + 1 左边等号成立当且仅当t 竺r ；右边等号成立当且仅当t 竺& 由引理1 ，有：若u u 是g 的一条边，则z ( g ) 名( g 一伽) 而且，若g 至 少有一条边，则z ( g ) z ( g 一秽) 一5 高校教师在职硕士学位论文 1 3 图的几个基本变换 为了我们讨论的方便，我们介绍下面几个图的变换 变换i ( 【1 1 ，1 5 】) 设g 最，是一个简单连通图u y ( g ) ，g 。表示将u 与简单路 1 耽，1 七 z ( g ) 或z ( g 2 ) z ( g ) ； ( i i ) t ( g 1 ) i ( g ) 或i ( g 2 ) i ( g ) 说明2 经过若干次变换i 后，若我们重复变换i i ，任何围长为9 的单 圈图变成氕措，以及h o s o y a 指数增大，m e r r i 丘e l d - s i m m o n s 指数减小 变换i i i ( 【1 2 ，1 4 】) 设伽是图g 的一条边，g ( u ) = ，叫l ，耽，虮，其 中伽1 ，耽，奶为g 中的叶子g ，- g 一 u 硼l ，t 正2 ，t 正叫。】+ u 伽l ，u 她，钐叫。) 如图1 3 4 所示 g 恐 i i i 她 “1 地 图1 3 4 变换i i i 引理6 ( 【1 2 ，1 4 】) 设图g 是由g 经过变换珊得到的图，则 ( i ) z ( g 7 ) t ( g ) 说明3 经过若干次变换i i i 后，单圈图中不在圈上的边变成悬挂在圈 上的悬挂边，以及h o s o y a 指数减小，m e r r i f i e l d s i m m o n s 指数增大 变换i v ( 【1 2 ，1 4 】) 设t ，u 。是图g 的两个顶点，u 。，u 2 ，t 。是连接在顶 点u 上的叶子，u ，也，仇是连接在顶点 上的叶子 g 7 = g 一 t 正u 1 ，t 上u 2 ，t 正u s ) + u t 正l ，u u 2 ，口u 。) ； g = g 一 u u l ，u u 2 ，u u t ) + t 口1 ，t 忱，让仇， 如图1 3 5 所示 g t 正1 u 0 u 1 仇 夕 。 i v 图1 3 5 变换i v s + 。 j 、 is + j 引理7 ( 1 2 ，1 4 】) 设图g ，g 是由g 经过变换i v 得到的图，则 ( i ) z ( g ) t ( g ) 说明4 经过若干次变换i i i 后，若我们重复变换i v ，任何围长为9 的 单圈图变成g 捃，以及h o s o y a 指数减小，m e r r i i i e l d s i m m o n s 指数增大 在下面的章节中，我们利用这四个图的变化讨论单圈图的h o s o y a 指 数与m e r r i 丘e l d - s i m m o n s 指数 8 1 4 主要结论 定理1 设n 1 1 ，在礼阶单圈图中，有 z ( g 绍) z ( g 嚣) z ( g 错) z ( g 珏) 名( g 嚣) z ( g 器) = z ( g 船) z ( g 撼) i ( 喇) ( 喇) i ( 剃) ( 9 器) i ( 喇) = i ( 鲥) 陕卜一 蜊 1匕 p _ 5 谈卜一6 联 _ 冻卜一5 图1 4 3 1 0 鲥 单圈图依h o s o y a 指数与m e r r i f i e l d s i m m o n s 指数的排序 2 单圈图的h o s o y a 指数序 本章中，我们将利用上面提到的几个图的变换得到h o s o 归指数前八 小的单圈图，以及h o s o y a 指数最大，次大的单圈图 首先介绍几个已知的结论 引理2 1 ( 【1 1 】) 设g 钾，则z ( g ) z ( g 嚣) 等号成立当且仅当g 竺 g 嚣 对于给定的整数夕3 和仃之9 础的h o s o y a 指数为z ( g 嚣) = f ( 9 1 ) + f + 1 ) + ( n 一9 ) f ( 9 ) 定理2 1 1 设夕4 ，则z ( g 嚣) z ( g 笋1 ，1 ) 证明由上可得 = z ( g 嚣) 一z ( g 婴1 ，1 ) = f ( 夕一3 ) + f ( 9 一1 ) 一f ( 9 1 ) + ( n 一夕) f ( 9 2 ) = ( n 一9 ) f 国一2 ) + f ( 9 3 ) 0 定理得证 定理2 1 2 ( 【1 8 】) 设g 为一任意的n 阶单圈图，9 4 若g g 嚣则 z ( g ) 2 f ( 9 + 1 ) + ( n 一9 + 1 ) ( f ( 9 ) + f ( g 一2 ) ) ，等号成立当且仅当g 垡g 豫 。与定理2 1 1 的证明类似，我们得到下面的结论 定理2 1 3 设夕3 ，则z ( g 髯l ，2 ) 名( g 爨) 证明由上面的定理，可得 名( 掣。，：) 一z ( 掣) = 2 f ( 夕+ 2 ) + ( n 一9 ) ( f b + 1 ) + f ( 9 1 ) ) 一2 f ( 9 + 1 ) 一( n 一9 + 1 ) 【f ( 9 ) + f ( 夕一2 ) 】 = f ( 9 1 ) + ( n 一夕) 【f ( 9 1 ) 一f ( 夕一3 ) 】 o 引理2 2 ( 【1 8 1 ) 设g 是n 个顶点的单圈图，则 ( i ) z ( g ) 2 n 一2 ，等号成立当且仅当g 型g 料； 一1 1 高校教师在职硕士学位论文 ( i i ) 若g g 埘，则z ( g ) 3 n 一6 ，等号成立当且仅当g 型g 珏 一1 2 单圈图依h o s o y a 指数与m e r r i f i e l d s i m m o n s 指数的排序 2 1 单圈图的最小h 0 8 0 弦指数序 在本节中，我们将按照单圈图的围长来分类讨论单圈图的h o s o y a 指 数序 情形( 1 ) 围长9 = 3 时： 设，n 是将星图k ，m 与k 。一的“中心钟( 即非悬挂点) 用一条边连 接得到的图由，住的定义，容易计算得到岛，。的h o s o y a 指数，z ( ，n ) = 仇n + m + n + 2 设咫= 昂西，加+ 口+ r + 3 = n ) 表示所有形如昂，口，的n 阶图的集合 定理2 1 4 当p 口r o 时，得z ( 昂+ 1 ，。吐，) 0 定理得证 设g 嚣是将k ，加s 与k ，：分别粘接到伤上的两个相邻顶点得到的 图如图2 1 1 ( a ) g 茹是将k ，。一6 与k 。，3 分别粘接到g 上的两个相邻顶 1 3 高校教师在职硕士学位论文 点得到的图如图2 1 1 ( b ) g 缎是将，n s 粘接到g 的一个顶点上，以及 将k ，2 分别粘接到岛的另外两个顶点上得到的图如图2 1 1 ( c ) g 嚣是 将k l ，n - 6 ，k 1 ，2 与鲍分别粘接到g 的三个顶点得到的图如图2 1 1 ( d ) a g 撼 1 n 一5 j 1 扎一6 j c g 豫 1 佗一5 j 1 扎一6 j b g 材d g 嚣 图2 1 1 由上图，可以计算出： z ( g 嚣) = 4 n 一1 2 ，z ( g 珏) = 5 n 一2 0 ， z ( g 嚣) = 5 n 一1 6 ，z ( g 象) = 7 n 一3 0 从而由定理2 1 4 以及上面的计算，得 定理2 1 5 当n 9 时，有z ( g 嚣) z ( g 缨) z ( 础) z ( g 嚣) 则由引理4 ，5 以及定理2 1 4 ，2 1 5 有 定理2 1 6 当n 9 时，醯中的图按照h o s o y a 指数的一个排序为 z ( g 黜) 名( g 珏) z ( g 器) z ( g 嚣) 名( g 象) z ( g 象) o 定理得证 1 5 高校教师在职硕士学位论文 定理2 1 8 z ( 见从1 ) z ( 凰，0 n 一4 1 ) ，等号成立当且仅当尼，矗女，f 竺岛 o n 一4 ，1 证明由定理2 1 7 ，z ( 足m 1 ) z ( 见卅眦1 ) 经过若干次变换，由引理1 6 ， 1 7 ，若g 忍挑l ，则z ( g ) z ( r 一5 ，o l 1 ) ，或z ( g ) z ( 凰，0 ，。“1 ) ，或z ( g ) z ( 风0 ，1 矿4 ) 下面，我们只要比较z ( 心吨0 l ，1 ) ，z ( 凰，o 1 。一4 ) 与z ( 风 0 ，。“1 ) 经过简单计算，得z ( 风吨o ，1 1 ) = 5 几一1 5 ，z ( 风t 0 ，n - 4 1 ) = 4 他一1 0 ，z ( 风，0 1 1 胪4 ) = 4 n 一1 0 从而z ( 忍_ 5 o 1 ，1 ) z ( 风，o 扩4 ，1 ) = z ( 风，o ，1 。4 ) 凰 o t n “1 记为g 绍，岛，0 l 加4 记为g 器，r _ 5 ，o 1 ，1 记为g 鳃 定理2 1 9 设n 1 1 ，有 ( i ) 名( g ! 二) 名( g 器) ； ( i i ) z ( g 埘) z ( g 器) 证明由前面的讨论，有 z ( g 器) = 4 n 一1 0 ，z ( g 撼) = 4 n 一1 2 ，z ( g 珏) = 5 n 一2 0 比较就可以得出 结论 定理得证 为简单记，风，o ， 1 表示为风，l 且尼+ l + 3 = n 定理2 1 1 0 设n 6 ，后1 ，七+ f + 3 = n ，得z ( g 撼) z ( g 嚣) 若2 l ，n 一4 ，则m i n 【z ( 风，1 ) = 6 n 一2 2 ，等号成立当且仅当z = 2 或 f = n 一5 定理得证 综合以上讨论得 定理2 1 1 1 设g 彩7 ：，则 1 6 单圈图依h o s o y a 指数与m e r r i f i e l d s i m m o n s 指数的排序 ( i ) 名( g ) 4 n 一1 0 等号成立当且仅当g 笺g 辩或g 笺g 鳃 ( i i ) 若g 笋g 器，g 筘，则z ( g ) 5 礼一1 5 等号成立当且仅当g 垒g 器 定理2 1 1 2 设礼1 1 ，钾中h o s o y a 指数序为 z ( g 料) z ( g 嚣) z ( g 始) z ( g 翁) = 2 ( g 筘) z ( g 射) 2 ( g 躲) z ( g 器) 情形( 2 ) 围长为9 = 4 时： 类似于9 = 3 ，当9 = 4 时，设钟表示围长为4 的单圈图的集合则 定理2 1 1 3 设g 研，则 ( i ) z ( g ) 轨一5 等号成立当且仅当g 冬g 料； ( i i ) 若g 笋g 料，则z ( g ) 4 扎一1 0 等号成立当且仅当g 型g 搭； ( i i i ) 若g 笋g 措，g 姥，则z ( g ) 5 他一1 5 等号成立当且仅当g 兰g 镏， 其中g 瓣表示在q 的两个相邻顶点上分别连接与k - 扩5 得到的单圈 图 情形( 3 ) 围长为夕= 5 时： 此时我们知道，h o s o y a 指数最小的是g 嚣且名( g 器) = 5 n 一1 4 比较以上三种情形，得以下的结论 定理2 1 1 4 设扎之8 ，有 ( i ) z ( g 埘) 2 ( g 嚣) ； ( i i ) z ( g 姥) = z ( g 器) = z ( g 筘) ； ( i i i ) z ( g 黯) = z ( g 嚣) z ( g 黜) 综合以上所有的结果，得到单圈图关于h o 哪指数的一个排序 定理2 1 1 5 设n 1 1 ，在礼阶单圈图中，有 z ( g 嚣) z ( g 器) z ( g 嚣) z ( g 撼) z ( g 嚣) = z ( g 器) = z ( g 始) 1 7 高校教师在职硕士学位论文 z ( g 嚣) z ( g 嚣) 【气p j z ( 爿禺，1 ) = f ( n + 1 ) + f ( 9 3 ) f ( n + 3 9 ) 令，- z ( 咒嚣) 一z ( 咒，。) ，则当9 【詈j + 2 时，同样有 f ( 9 1 ) f ( n + 1 9 ) 一f ( 9 3 ) f ( n + 3 9 ) = 【f ( 9 2 ) + f ( 9 3 ) 】【f ( 佗+ 3 一夕) 一f ( n + 2 一g ) 】 一f ( 9 2 ) f ( n + 3 9 ) = 一【一f ( 9 2 ) f ( 几十3 9 ) + f ( 9 1 ) f ( n + 2 9 ) 】 = ( 一1 ) g 一2 【_ - f ( 1 ) f ( n + 6 2 夕) + f ( 2 ) f ( n + 5 2 9 ) 】 = ( 一1 ) 口一1 f ( n + 4 2 9 ) 从而 ( i i i ) 当n 为偶数时， ，： ( 一1 ) g 一1 f ( n + 4 2 夕) ， 6 9 【鸶j + 2 ； 【 ( 一1 ) g f ( 2 9 亿一4 ) ， 夕 【詈j + 2 ( i v ) 当礼为奇数时， ( 一1 ) 9 1 f ( 扎+ 4 2 9 ) ， 5 g 【号j + 2 ； ( 一1 ) 9 1 f ( 2 9 一亿一4 ) ， 9 【鸶j + 2 z ( 咒艘) = f ( n 十1 ) + 2 f ( n 一3 ) ； z ( h 罂2 1 ) = f ( 礼+ 1 ) + 2 f ( 死一3 ) 一2 0 一 单圈图依h o s o y a 指数与m e r r i 6 e l d - s i m m o n s 指数的排序 结合( i ) ( i v ) ，在g 中能够取得最大的h o s o y a 指数的情况只能够 是在咒埘和冗婴。，。之间，但是z ( h 婴：。) = z ( 7 l f 埘) ，从而，在破g 中h o 哪，a 指数最大的是h 船和7 l f 罂： 1 证明完成 2 1 高校教师在职硕士学位论文 3 单圈图关于m e r r i f i e l d - s i m m o i l s 指数的排序 本章将利用图的变换研究单圈图关于m e r r i f i e l d s i m m o n s 指数的一个 排序首先得出单圈图的m e r r i l i e l d s i m m o n s 指数，然后再考虑排序问题 定理3 1 设g 呦是任意的一个单圈图，其圈为g 则i ( g ) t ( g 错) 等号成立当且仅当g 垒g 增 证明在图g 上重复变换i i i ，则g 变换成g ，在g ，中不在圈g 上得 边全部为悬挂边由引理6 ，得i ( g ) i ( g ) 接下来，在g 7 上重复变换i v ， g 7 变换成图g ，在g 上所有的悬挂边全部连接在g 的一个顶点u 上，从 而g 型g 艘由引理7 ，得i ( g 跚) t ( g ，) 最后，得i ( g ) i ( g 艘) ，等号成立 当且仅当g 皇g 艘 定理得证 对于给定的整数3 七几g 鼹的m e r r i f i e d s i m m o n s 指数为i ( g 锹) = f ( 尼一1 ) + 2 ”一七f ( 七+ 1 ) 定理3 2 设七3 ，有i ( g 错) i ( g 髀1 1 ) 证明由上，得i ( g 路) = f ( 七一1 ) + 2 ”一f ( 七+ 1 ) 则 = i ( g 跚) 一i ( g 肄1 1 ) = f ( 七一1 ) + 2 ”一七f ( 七+ 1 ) 一f ( 七) 一2 n 一七一1 f ( 七十2 ) = 2 n 一一1 f ( 七一1 ) 一f ( 七一2 ) 0 定理得证 定理3 3 ( 【1 1 】) 设g 七钟g 料为任一单圈图，则i ( g 七) i ( g 铧1 2 ) ms l ，m ，。为上一章所定义的图，则，n 的m e r r i f i e l d - s i m m o n s 指数为 ( ，。) = 2 m + n + 2 m + 2 n 定理3 5 当f m n o ，得i ( & + l ，一1 ，n ) i ( 岛，m ，n ) 和l ( & ，m + l n 1 ) 2 2 单圈图依h o s o y a 指数与m e r r i f i e l d s i m m o n s 指数的排序 i ( 岛，m ，n ) 证明首先，计算s l m 竹的m e r r i f i e l d - s i m m o n s 指数 i ( s ，m n ) = i ( & 一l ，。n ) + 2 卜1 i ( s n ，n ) = i ( 岛一2 m ，n ) + 2 。一2 i ( 5 k ，n ) + 2 一1 t ( 岛，作) = i ( 岛，m ，住) + ( 2 。一1 ) i ( 南，。) = 2 ”+ n 州+ 2 ”+ ”+ 2 件“+ 2 l + m =2 ”+ n + 1 + 2 m + 2 n 所以，有 1 = i ( & + 1 ，。一1 ，。) 一i ( 昌，。，。) = 2 件n 一2 ”+ n l = 2 “( 2 一2 ”一1 ) 0 2 = i ( & ，m + 1 俨1 ) 一 ( s l ，m 。) = 2 l + m 一2 ”+ l 一1 = 2 ( 2 ”一2 n 一1 ) o 定理得证 按照前面的推理思想，下面的讨论将按照围长大小来来分类讨论 情形( 一) ：9 = 3 设g 嚣，g 嚣，g 嚣，g 嚣分别是前面所描述的图，它们的m e r r i f i e d - s i m m o n s 指数分别为： i ( g 嚣) = 9 2 ”一5 + 4 ，i ( g 绁) = 1 7 2 n 一6 + 8 ，t ( g 裂) = 8 2 n 一5 + 4 ， ( g 粱) = 1 4 2 n 一6 + 8 从而可得 定理3 6 当n 9 时，有i ( g 嚣) t ( g 措) t ( g 器) l ( g 嚣) 醯为前所述的图则由引理6 ，7 和定理3 5 ，3 6 得 定理3 7 当n 9 时，咫中的图关于m e r r i 丘e l d s i m m o i l s 指数的排序为 i ( g 嚣) t ( g 嚣) t ( g 嚣) i ( g 珏) i ( g 嚣) i ( g 嚣) 2 3 高校教师在职硕士学位论文 彩景为第二章中所描述的图显然，彩景= 叼一艮由引理6 ，7 ，在 钐景中具有最大m e r r i l i e l d - s i m m o n s 指数的图必然是由k l l ( 2 1 ) 连接在 & ，j ，k ( i ，j o ，忌1 ) 的一个悬挂点上，记这样的图为r ，j ，七 1 同定理3 5 的证明方法一样，得 定理3 8 设i 歹l ，有t ( r + 1 j l ，k ，1 ) i ( r ，j k ，1 ) 特别的，i ( r ，七，j ) i ( 忍+ m k ，1 ) 证明r 五七，l 的m e r r i l i e l d - s i m m o n s 指数为