（运筹学与控制论专业论文）具有完美匹配的仙人掌图的谱半径及其randic指数下界.pdf

摘要 设g = ( ve ) 是一个简单连通图，v ( c ) 和e ( c ) 分别为g 的顶点集 和边集设入1 ；a 2 ；h 是图的特征多项式d e t ( a i a ( g ) ) 的n 个特征值， 我们称最大的特征值为图g 的邻接谱半径图的r a n d i d 指数是化学图论 中一个重要的拓扑指数，在化学中有着许多的应用，并得到了广泛的研究 而这种指数定义为r ( g ) = ( d ( 牡) d ( 移) ) 一 ，其中d ( 珏) 和d ( 钞) 分别表示图 u v e ( g ) g 中顶点越和秽的度数 一个简单连通图g 称为仙人掌图，是指图g 中的任意两个圈之间至 多有一个公共点够( n ，k ) 表示圈数为k 且具有完美匹配的2 n 个顶点的 仙人掌图的集合，r ( g ) 表示图g 的r a n d i d 指数本文刻画了够( n ，k ) 中 具有最大谱半径的仙人掌图，同时给出够( n ，七) 中r a n d i d 指数的下界：若 g 够( n ，七) 【风，日8 ) ，n 2 ，则r ( g ) 曩赫+ 赤+ 学+ 哗，其中 风，凰在图3 _ 1 中已描绘 关键词：谱半径；r a n d i d 指数；仙人掌图；完美匹配 a bs 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 hw i t ht h ev e r t e xs e tv ( a ) a n dt h ee d g es e te ( g ) l e ta t ；a 2 ；ka r ea l l 扎e i g e n v a l u e so ft h ec h a r a c t e r i s t i c p o l y n o m i a ld e t ( a i 一4 ( g ) ) o fg ，w h e r et h el a r g e s te i g e n v a l u ei sc a l l e dt h es p e c t r a l r a d i u so fg t h er a n d i di n d e xo ft h eg r a p hi so n eo ft h em o s ti m p o r t a n tt o p o l o g i c a l i n d i c e si nc h e m i c a lg r a p ht h e o r y i th a sal o to fa p p l i c a t i o n si nc h e m i s t r ya n db e e n w i d e l yi n v e s t i g a t e da sw e l l a n dt h er a n d i di n d e xo ft h eg r a p hg i sd e f i n e da s 冗( g ) =( d ( t 正) d ( ) ) 一i ，w h e r ed ( u ) a n dd ( u ) a r et h ed e g r e e so fv e r t i c e st 正a n d u v e e ( g ) 口i ng ，r e s p e c t i v e l y w es a yt h a tt h eg r a p hgi sac a c t u si fa n yt w oo fi t sc y c l e sh a v ea tm o s t o n ec o m m o nv e r t e x t h es e to fc a c t iw i t hkc y c l e sa n dp e r f e c tm a t c h i n g so i l2 n v e r t i c e sa r ed e n o t e db y 够( 礼，k ) a n dt h er a n d i di n d e xo fag r a p hgi sd e n o t e db y r ( g ) i nt h i sp a p e r ，t h eg r a p hw i t hl a r g e s ts p e c t r a lr a d i u si su n i q u e l yc h a r a c t e r i z e d a n das h a r pl o w e rb o u n do fi n d e xo fr a n d i di sa l s og i v e na m o n gg 够( 扎，七) ：i f g 够( 礼，七) 风，风) ，凡之2 ，t h e nr ( g ) 黄器+ 赤+ 哥+ 毕，w h e r e 日6 ，8a r ed i s p l a y e di nf i g u r e3 - 1 k e y - w o r d s ：s p e c t r a lr a d i u s ；r a n d i di n d e x ；c a c t u sg r a p h ；p e r f e c tm a t c h i n g s i i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果除文中已经注明引用的内容外，本论文不含任 何其他个人或集体已经发表或撰写过的作品成果对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明本人完全意识到本声 明的法律结果由本人承担 学位论文作者豁垆 嗍车钿朋 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留，使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅本人授权湖南师范大学可以将学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印，缩印或扫描等复制手段保 存和汇编本学位论文 本学位论文属于 1 、保密口，配年解密后适用本授权书 2 、不保密d ( 请在以上相应方框内打誓 矗) 作者签名；力多矽日期。夕矽年月名 导师签名；邵洱以日期：沙吕年多月，d 日 l 具有完美匹配的仙人掌图的谱半径及其r a n d i d 指数下界 1 引言和基本概念 1 1 引言 图论是一门应用广泛的数学分支，是处理离散数学问题的强有力工 具；同时也是运筹学、计算机科学、电路网络研究类和实践应用中不可缺 少的数学工具不仅如此，现今在物理学、化学通讯工程、社会科学等各 种领域都有广泛的应用 图谱理论是图论中的一个非常活跃研究方向，其研究主要是利用成 熟的代数理论和技巧，并结合图的拓扑结构性质、组合数学的理论和矩阵 理论来研究图谱及其与图的结构性质、图的其他不变量( 如色数，度序列， 直径，连通度等) 之间的关系图谱理论的研究与发展有着重要的理论和 实践意义，近些年来在国内外的学术刊物和专著中发表了关于图谱的许 多研究文章，不断地丰富和促进这门学科的发展 尤其在化学中，图论的应用已涉及合成化学、聚合化学、量子化学及 化学信息的存储和检索等领域，最大量的应用集中在定量结构活性性 质相关性( 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 ) 中非常有用，这些指数中有些是基于 图中点的距，有些是基于图中点的度数 在1 9 7 5 年，m r a n d i d 2 2 1 提出了如下r a n d i d 指数( 也称为连通指数) 定 义为： r = r ( g ) = ( d ( u ) 荆) 一 u v e e ( a ) 其中d ( u ) 和d ( v ) 分别表示图g 中顶点t 和钌的度数，e ( g ) 为图g 中的 边集r a n d i d 证实了他的指数与各种有机化合物的物理化学性质密切相 硕士学位论文 关r a n d i 6 指数立刻被成功地广泛应用到许多物理，化学，生物性质中( 如 沸点，溶解度，密度等) ，像其它拓扑指数一样，r a n d i 6 指数引起了许多数学 家和化学家的极大关注后来，这种结构的描述成为应用最多的的一种拓 扑指数之一许多的文献中都探讨了它，其结果出现在大量的科学论文和 两本著作中 2 6 ，2 7 】 近些年来，研究一些特殊图类的谱半径和r a n d i d 指数都是许多的数学 家和化学家研究的主要方向 关于一些特殊图类的谱半径，主要有以下一些结果： ( 1 ) 在所有的连通图中，r a b r u a l d i 和e s s o l h e i d 4 1 刻画了连通图中最 大谱半径的图； ( 2 ) 对于树，j g u o 和s t a n 9 】给出了树的谱半径的上界；g x u 1 0 1 研究 具有完美匹配的树并刻画了这类树中前7 大谱半径的树； ( 3 ) a b e r m a n 和x z h a n g 1 3 】研究具有割点的图类，并刻画这类图中最 大谱半径的图；h l i n ，m l u 和f t i a n 1 4 】研究具有割边的图类，并刻画了这 类图中有最大谱半径的图； ( 4 ) a c h a n g 和f t i a n 1 5 ，1 6 】研究了具有完美匹配的单圈图，双圈图， 并分别刻画了这类图中最大谱半径的图 关于一些特殊图类的r a n d i d 指数，主要有以下一些结果： ( 1 ) 对于n 阶连通图，b b o l l o b 五s 和p e r d s s 2 9 】给出了这类图r a n d i 6 指 数的下界； ( 2 ) 对于最小度为2 的图，c d e l o r m e ，o f a v a r o n 和d r a u t e n b a c h 4 4 】给 出了这类图r a n d i 6 指数的下界； ( 3 ) 对于树，路r 和星图晶分别为r a n d i 6 指数最大值，最小值的图； 对于单圈图，g a o 和l u 3 8 】给出了这类图r a n d i d 指数的上界和下界； ( 4 ) 对于无圈共振分子图，m l u ，l z z h a n g 和f t i a n 3 9 1 给出了这类图 r a n d i 6 指数的下界； ( 5 ) 对于单圈共振分子图，h q l i u ，x f p a n 和j m x u 4 0 】给出了这类 一2 - 具有完美匹配的仙人掌图的谱半径及其r a n d i d 指数下界 图r a n d i d 指数的下界； ( 6 ) 对于仙人掌图，m l u ，l z h a n g 和f t i a n 4 2 给出了这类图r a n d i d 指 数的下界 ( 7 ) 对于( n ，m ) 一化学图，x l i ，x w a n g 和b w e i 4 5 】给出了这类图r a n d i d 指 数的上界和下界； 一3 - 硕士学位论文 1 2 基本概念和基本术语 本文所研究的图均为无环，无重边，有限无向的简单连通图所有的 专业术语均可参考文献 1 】 设图g = ( ve ) ，其中y 为顶点集，v = v ( a ) = 1 臼1 ，v 2 ，) ，i v i = n 称为图g 的阶数，e 为边集，e = e ( g ) = e 。，e 。，e m ，i e l = m 为图g 的 边数，若e 的两端点分别为顶点牡与t ，记为e = 删或1 1 , 一移，则称顶点u 与廿相邻接否则称它们不相邻，记为u 和t ，与口相关联的边的个数称为 口的度，记为d ( u ) 对于连通图g 中，用d ( u ，口) 表示两个顶点u ，口之间的距 离，g ( v ) 表示顶点凹在图g 中所有邻点组成的集合 图g 的邻接矩阵记为a = a ( g ) = ( ，) n 撕是一个n 阶的( 0 ，1 ) 一方阵， 其定义如下 = r ：荔 显然= o ，= 哟t ，故而a ( g ) 是一个实对称方阵我们称d e t ( m a ) 为图g 的特征多项式，记为p ( a ) 或p ( g ；a ) 它的特征值入。，入2 ，k 均 为实数，不妨将其从大到小排列为入- ( g ) a z ( g ) h ( g ) 我们记 入( g ) = 九( a ) = 人，( i = 1 ，2 ，几) ，称 s p e c g = 入1 ( g ) ，入2 ( g ) ，k ( g ) 为图的邻接谱，其中最大特征值入。( g ) 也称为图g 的邻接谱半径，简称 图g 的谱半径，记作a ( g ) 当图g 连通时，a ( g ) 是一个非负不可约矩 阵，根据p e r r o n - f r o b e n i u s 定理，入( g ) 为单根，并存在一个单位特征向量z = ( z 。，2 ；2 ，) ? 与a ( g ) 相对应，即x i 0 ，a ( g ) x = a ( g ) z ，其中戤对应于顶 点饥，( i = 1 ，2 ，死) ，称z 为a ( g ) 的p e r r o n 向量，简称g 的p e r r o n 向量 对于图g = ( ve ) ，z ，y y ( g ) ，x y e ( g ) ，用符号g z 表示图g 去掉 点t ，及与点口相关联的边后所得子图；用g x y 表示图g 去掉边x y 后的 子图类似的，若x y 碧e ( g ) ，用g + x y 表示图g 增加边x y 的子图度数 为1 的点称为悬挂点，用符号p v 表示图g 中所有悬挂点组成的点集；同 4 具有完美匹配的仙人掌图的谱半径及其r a n d i d 指数下界 样的，与悬挂点相关联的边则称为悬挂边没有割点的连通图称为块记 6 ( a ) = m i n d ( v ) ：u y ( g ) ) 表示图g 的最小度我们用& ，g ，r 分别表示 ，1 个顶点的星图，圈，路 设m 是e ( a ) 的一个子集，m 中的任意两条在g 中均不相邻，则称m 为g 的匹配( 对集) ，m 中一条边的两个端点称为在m 下配对的若匹配 m 的某条边与顶点口关联，则称m 饱和点口，并且称移是m 饱和的，否则 称 是m 非饱和的若g 的每个顶点均为m 饱和的，则称m 是为图g 的 完美匹配 一个简单连通图g 称为仙人掌图【1 9 ，4 3 】，是指图g 中的任意两个圈 之间至多有一个公共点( 即边不交) ，从而引伸仙人掌图另一种定义，即图 g 每个块是圈或者是边 在仙人掌图中，若图g 的所有的圈恰好只有一个公共点，称g 为 誓丛力( b u n d l e ) 记够( 死，k ) 为圈数为k 且具有完美匹配2 死个顶点的仙人掌 图的集合设g 够( n ，七) ，若g 是丛，且每个圈的长度均为3 ，以及n k 一1 条长为2 的路和一条悬挂边粘在这k 个圈的公共点上，则把这样的仙人掌 图记为g ( 终，k ，o ) 特别地，当k = 孔一1 时，图为g ( n ，礼一l ，o ) ，如图1 1 所示 k 。- - - - i 一、 n 一1 ，l 、_ - - - 、_ 。、i 一 扎一k 一1 a ( n ，k ，0 )a ( n ，n 一1 ，0 ) 图1 - 1 一5 一 硕士学位论文 1 3 本文主要内容 1 - 在第2 章中，我们刻画了够( n ，k ) 中唯一具有最大谱半径的仙人掌 图主要结果如下： 定理2 2 1 若g 够( 死，七) ，除n = 3 且k = 1 外，则 入1 ( g ) a i ( g ( n ，k ，o ) ) ， 等号成立当且仅当g 垡g ( 讫，七，o ) 特别地，当k = 0 ，k = 1 时，够( 钆，o ) ，够( 死，1 ) 分别表示具有完美匹配2 他 顶点的树的集合，单圈图的集合 推论2 2 2 ( 1 0 】) 若t 够( 礼，o ) 则a 1 ( g ) 入，( g ( n ，0 ，o ) ) ，等号成立当且 仅当t 笺g ( n ，1 ，o ) 推论2 2 3 ( 【1 5 】) 若g 够( n ，1 ) ，n 4 则a 1 ( g ) 入l ( g ( 佗，1 ，o ) ) ，等号成 立当且仅当g 竺a ( n ，1 ，o ) 推论2 2 4 在所有具有完美匹配2 礼个顶点仙人掌图中，图a ( n ，n 一1 ，0 ) 具有最大谱半径 2 在第3 章中，我们给出够( 礼，k ) 中r a n d i d 的下界，并唯一刻画了达到 下界的图a ( n ，k ，o ) 主要结果如下： 定理3 3 1 若g 够( 亿，k ) 风，风) ，礼2 则n ( g ) 妒( n ，七) ，等号成 立当且仅当g 竺a ( n ，k ，o ) ，其中风，风是图3 - 1 ( 见1 7 页) 所描绘的两个图 6 一 具有完美匹配的仙人掌图的谱半径及其r a n d i 6 j 旨数下界 2 够( n ，尼) 中具有最大谱半径的图 在图谱理论中，图的谱半径的研究一直以来都是一个热点问题，给出 一类图的最大谱半径，对于了解图的特征有十分重要的意义 2 1 主要引理 近年来众多的学者研究关于一些图类的谱半径的结果，在这方面图 的谱半径的有关结果还在不断地丰富和改进而p e r r o n - f r o b e n i u s 定理是 研究谱半径的一个很重要的工具下面八个引理在相关的研究中将起到 重要的作用 引理2 1 1 ( 2 0 】) 设t ，t ，是连通图g 的任意两个顶点，s 为某一整数，若 v l ，也，) n ( v ) ( t ) ( 1 s d ( 钉) ) 且z = ( 2 ；1 ，2 ；2 ，z n ) 是g 的 p e r r o n 向量将g 中边t 7 仇替换为u v ；( 1 主s ) 得到图g ，若气，则 入1 ( g ) a 1 ( g ，) 引理2 1 5 ( 2 1 1 ) 设牡，t ，是图g 的两个不同顶点，若在g 中，t ，t ，分别粘 有s ，t 条长为2 的路，记图g 为g 础，则 入1 ( g 。+ i ，t i ) a 1 ( g ，t ) ( 1 主t ) 或 入1 ( g 。一t ，t + ) a 1 ( g ，t ) ( 1 主s ) 非平凡连通图日的一个顶点与树t 的一点粘合，得图g 如图2 - 2 所 示，在图g 中称粘合点r 为树t 的根若图g 具有完美匹配，则有下面引 理2 1 6 ： 图2 - 2 g 引理2 1 6 ( 【1 5 】) 若图g 有完美匹配，口y ( t ) ( 秽r ) 离根，的最远点， 则可是悬挂点且其邻点心的度为2 图g 是图2 - 2 所描绘的图且具有完美匹配，记i y ( t ) l 为粘合树t 的顶 点数( 不包含根，) 假设l 矿( t ) i 2 ，若t ，是树t 中离根r 最远的顶点，因 图g 有完美匹配，由引理2 1 6 ，其邻点钍的度为2 现在我们对图g 进行 移接变形，令g 。= g 一叫札+ r u ，所得图g 。仍具有完美匹配，如图2 - 3 所示 在图g 。中，若l v ( t t 一秽) i 2 ，则对图图g 。进行上述移接变形，因而最 终，如果l y ( t ) i 是奇数可得到图g o ，如果i y ( t ) l 是偶数可得到图日o 则有 下面引理2 1 7 成立： 8 一 具有完美匹配的仙人掌图的谱半径及其r a n d i 6 指数下界 g g 1 图2 - 3 图g 及其变形后的图g 1 g o 图2 4 图g o ；图日。 引理2 1 7 ( 1 5 】) 设g ，g o ，凰是图2 - 3 ，图2 4 中描述的图对于a 入1 ( g ) ，则p ( g ；入) p ( g o ；入) 或p ( g ；入) p ( h o ；入) 特别地，都有a 1 ( g o ) 入1 ( g ) ，入1 ( h o ) 入1 ( g ) 由于图的特征多项式的根是实数，本章中，我们仅对含实根的多项式 进行考查，设i ( x ) 是关于z 的多项式，记，( z ) 的度为a ( ，) ，( z ) 的最大根 为入。( ，) 下面给出一个比较两多项式最大根大小的有效方法 引理2 1 8 设，( z ) ，夕( z ) 为有实根的首一多项式且o ( f ) a ( 9 ) i ( x ) = q ( z ) g ( z ) + 7 ( z ) ，其中口( z ) 和r ( z ) 是多项式且o ( r ) a c g ) 若对于z a 1 ( 夕) ， r ( x ) 0 和g ( z ) 0 成立，则a l ( ，) 0 成立，则有g ( a 1 ( ，) ) 0 因此与，( a 1 ( 川= 一g ( a 1 ( 川夕( a 1 ( 川0 矛盾 一1 0 具有完美匹配的仙人掌图的谱半径及其r a n d i d 指数下界 2 2 够( n ，k ) 中具有最大谱半径的图 在本节中，我们刻画了够( n ，k ) 中具有最大谱半径的仙人掌图 首先，我们关注箩( 佗，k ) 中一类“丛图，记a ( n ，k ，i ) 为k 个圈圈长均 为3 ，且在这k 个圈的公共点v o 上粘有n k i 1 条长为2 的路和一条 悬挂边，和其中i 个圈每个顶点都粘一条悬挂边如图2 - 5 所示，我们给出 三个图a ( 8 ，3 ，o ) ，a ( 8 ，3 ，1 ) ，c ( 8 ，3 ，2 ) 涎莠一a ( s ，3 ，0 )a ( s ，3 ，1 )a ( s ，3 ，2 ) 图2 5 引理2 2 1 若n 7 ，则 ( i ) 对于i 0 ，e ( a ( n ，老，主) ；a ) = ( 爻2 1 尸一压一2 ( ，一3 入2 + 1 ) 一1 爻8 一( 死+ k 一 主+ 4 ) - 2 k a 5 + ( 3 n + 3 k 一5 t + 5 ) a 4 + ( 6 k 一4 i ) 入3 一( n + k i + 4 ) 入2 - 2 ( k 一云) 入+ 1 】； ( i i ) 对于0 i k 一1 ，入1 ( g ( n ，k ，i + 1 ) ) 入l ( & + h ) = 折再i = 可何和入1 ( 日) 何注意到入1 ( 入2 1 ) = l 及 入1 ( 入4 3 入2 + 1 ) 1 6 1 8 ，因而当n 3 时，则入1 ( g ) = 入1 ( 夕) 和入1 ( 日) = 入1 ( ，) 进一步地， ，( 入) = 夕( 入) + r ( 入) ，其中，( 入) = 入6 5 一4 a 3 + 入2 + 2 入很容易证，对于 入 2 5 1 2 时，( 入) 0 和当n 7 ，r ( 何) 0 都成立 因此对于a 入1 ( g ) = 入1 ( 夕) ，则，( 入) 0 由引理2 1 - 8 ，当死7 时，我们 直接得到结论入。( 夕) a 1 ( n 即a l ( g ) a l ( 日) 注：当n = 6 ，5 ，4 ，3 ，2 ，1 时，表2 - 1 和表2 2 ( 见1 3 页) 列出图g ( 礼，k ，i ) 及 其谱半径结合引理2 2 1 ，在所有的图类g g ( n ，k ，i ) i o i 七) 中，除 佗= 3 ，k = 1 时外，c ( n ，七，0 ) 具有最大谱半径 定理2 2 1 若g 够( 佗，七) ，除几= 3 且k = 1 外，则入1 ( g ) 入1 ( g ( n ，k ，o ) ) ， 等号成立当且仅当g 竺a ( n ，k ，o ) 一1 2 具有完美匹配的仙人掌图的谱半径及其r a n d i d 指数下界 n = l n = 2 n = 3n - 4 n = 5n = 6 k - - 0 g ( 1 ，0 ，0 )g ( 2 ，0 ，0 )g ( 3 ，0 ，0 )g ( 4 ，0 ，0 )g ( 5 ，0 ，0 )g ( 6 ，0 ，0 ) k - - 1 g ( 2 ，1 ，0 )g ( 3 ，1 ，0 )g ( 4 ，1 ，0 )g ( 5 ，1 ，0 )c ( 6 ，1 ，0 ) g ( 3 ，1 ，1 )g ( 4 ，1 ，1 )g ( 5 ，1 ，1 ) c ( 6 ，1 ，1 ) k = 2 g ( 3 ，2 ，0 )g ( 4 ，2 ，0 )g ( 5 ，2 ，0 )g ( 6 ，2 ，0 ) g ( 4 ，2 ，1 )g ( 5 ，2 ，1 )g ( 6 ，2 ，1 ) c ( 5 ，2 ，2 )c ( 6 ，2 ，2 ) k - 3 g ( 4 ，3 ，0 )g ( 5 ，3 ，0 )g ( 6 ，3 ，0 ) g ( 5 ，3 ，1 )g ( 6 ，3 ，1 ) g ( 6 ，3 ，2 ) k = 4 g ( 5 ，4 ，0 )g ( 6 ，4 ，0 ) g ( 6 ，4 ，1 ) k - 5 g ( 6 ，5 ，0 ) 表2 1 对于n = 6 ，5 ，4 ，3 ，2 ，1 ，图g ( n ，k ，t ) n = 1n = 2 1 1 = 31 1 = 4i i - - = 5 i i - - - - 6 k ：= 01 1 6 1 8 0 31 9 3 1 8 52 1 8 8 9 02 4 1 4 2 1 2 6 1 8 0 3 k = 12 1 7 0 0 92 3 7 9 8 82 5 7 4 1 12 7 5 5 7 42 9 2 6 8 7 2 4 1 4 2 12 5 6 0 6 22 7 1 1 7 02 6 8 3 3 8 k = 22 7 0 9 2 82 8 7 5 7 63 0 3 4 7 23 1 8 6 9 5 2 8 1 9 4 02 8 6 4 7 53 1 0 8 0 0 2 9 0 5 7 03 0 3 8 4 0 k = 3 3 1 3 2 6 4 3 2 7 6 8 73 4 1 6 2 3 3 1 9 6 1 83 3 3 1 0 0 3 2 5 2 2 6 k = 43 4 9 3 9 63 6 2 3 7 4 3 5 3 6 1 5 k = 53 8 1 4 7 9 表2 - 2 对于n = 6 ，5 ，4 ，3 ，2 ，1 ，图a ( n ，k ，i ) 的谱半径 一1 3 - 硕士学位论文 证明选择图g 够( n ，k ) 使其谱半径尽可能的大图g 顶点集v ( g ) = 口1 ，现，) 及其p e r r o n 向量为z = ( x z 抛，z 。) ，分量与顶点优 相对应m 是g 的一个完美匹配首先，我们证明图g 的所有圈的圈长为 3 且图g 是一个“丛 下面一起来证明三个断言： 断言1 图g 中圈的圈长全都为3 证明采取反证法，假设在图g 中存在一个圈长不小于4 的圈c ，记 圈c = u l u 2 u p u l ，p 4 不失一般性，不妨设u l u 2 ，坳唧一1gm 及z u 。z u p 令 g 。= g 一 坳邯一1 ) + u 1 唧一1 ) 那么g + 够( n ，七) ，由引理2 1 1 知a 。( g + ) a l ( g ) ，从而与图g 的选择 相矛盾 所以，图g 中圈的圈长全都为3 断言2 图g 中任意两圈之间恰有一个公共点 证明采取反证法，若在图g 中存在两个不相交的圈a 和c 2 ，则存在 一条长为p 一1 的路p = 乱。乱2 u p ( p 2 ) 连接圈g 和岛，其中圈g 与路 p 相交于点u t ，圈q 与路p 相交于点唧不失一般性，不妨设z t p 2 ；u 。 由断言1 知，圈a 的圈长为3 ，记q = u l v w u 。 如果u 。 m ，那么存在一个点w v ( v ) 使得w w 7 m ( i ) ， 令g = g 一 w w 7 + u w 7 ) ，则m = m 一 u l v + 口硼 也是g 的完美 匹配 ( i i ) z u 。 a 1 ( g ) ， 从而与图g 的选择相矛盾 1 4 具有完美匹配的仙人掌图的谱半径及其r a n d i d 指数下界 因此，牡。t ，gm 类似地，u l wgm 令 g = g 一 u 1 口，u l w + 口，坳切) 则入。( g ) 入1 ( g ) ，由引理2 1 1 知a - ( g + ) a 1 ( g ) ，从而与图g 的选择 相矛盾 所以，图g 中任意两圈之间恰有一个公共点 断言3 图g 中任意三个圈之间恰有一个公共点 证明由断言2 的证明知道，图g 的任意的两个圈之间恰有一个公共 点，若g 的任意的三个圈之间有两个或两个以上的公共点相同，则图g 就 不是仙人掌图，与题设矛盾 综合论断1 - 3 ，我们知图g 所有圈的圈长全都为3 ，且都相交于一公共 点，即图g 是一个誓丛嚣记q 丛靠中所有圈相交的公共点为v o 其次，如果树t 粘合在图g 的某一圈上顶点r ( r 是树t 的根) ，那么， 由引理2 1 6 和引理2 1 7 可证，树? 只能是长为2 的路或一条悬挂边，则 有： 断言4 图g 中圈上粘有的树仅为长为2 的路或仅为一条悬挂边( 如 图2 4 所示) 最后，我们证明下面两个断言 断言5 任何长为2 的路全都粘在公共点v o 证明采取反证法，设存在路p = u u t i ，粘在一点u ( 让铷) ，若牡c = v o u u l v o ，则伽，u t 1 m ( i ) z 如 令g = g 一 u 口) + 伽秒) ，则m 仍是g 的完美匹配 ( i i ) x v o 入1 ( g ) ， 从而与图g 的选择相矛盾 断言6 图g 必为某一图v ( n ，七，主) ( 0 主七) 证明采取反证法，若存在一条悬挂边粘在圈c = v o u u 。v o 上点u ( u 伽) ，而没其他悬挂边粘在点u 。，则伽m 。 ( i ) z 如 令g = g 一 伽】+ 珈钉) ，则m = m 一 伽u 1 ) + u u l ) 是g + 的完美匹配 ( i i ) z t j o 入1 ( g ) ， 从而与图g 的选择相矛盾 所以，g = v ( n ，k ，i ) 0 i k 再由引理2 2 1 以及表2 ，g = v ( n ，k ，o ) ，证毕 特别地，够( 礼，o ) ，够( n ，1 ) 分别表示有完美匹配2 n 点的树的集合，单圈 图的集合则有下面两个推论： 推论2 2 2 ( 1 0 】) 若t 够( n ，o ) 则入1 ( g ) 入1 ( g ( n ，0 ，o ) ) ，等号成立当且 仅当t 竺v ( n ，1 ，o ) 推论2 2 。3 ( 1 5 】) 若g 够( 1 ) ，死4 则a 1 ( g ) h ( g ( 珏，1 ，o ) ) ，等号成 立当且仅当g 竺a ( n ，1 ，o ) 注意到g ( 几，i 一1 ，0 ) 是g ( n ，i ，o ) ( 1 t k ) 的一个真子图由引理2 1 4 可知入1 ( g ( n ，0 ，o ) ) a 1 ( g ( n ，1 ，o ) ) 入1 ( g ( n ，n 一1 ，o ) ) 因此我们有下面 推论： 推论2 2 4 在所有具有完美匹配2 n 个顶点的仙人掌图中，图a ( n ，n 一 1 ，0 ) 具有最大谱半径 1 6 具有完美匹配的仙人掌图的谱半径及其r a n d i d 指数下界 3 汐( 礼，) 中r a n d i 封旨数的下界 3 1 主要引理 在拓扑指数中，r a n d i d 指数是一种重要的拓扑指数，它与不同种类的 有机化合物的物理一化学性质密切相关，其定义为 r ( g ) = ( d ( u ) d ( u ) ) 一主1 u v e e ( g ) 其中d ( u ) 和d ( 移) 分别表示图g 中牡和移两顶点的度数下面给出我们要 用到的六个引理 引理3 1 1 ( 【1 5 】) 若图g 有完美匹配，树t 粘在根r 上，口y ( t ) ( 口r ) 离根r 的最远点，则口是悬挂点且其邻点u 的度为2 引理3 1 2 ( 4 4 1 ) 设g 够( 礼，七) ，n 3 若p v ，对于点t y ( g ) ，则 i ( u ) n p y i 1 引理3 1 3 ( 4 4 1 ) 对于z 1 ，函数，( z ) 一f ( x b1 ) 为单调递增函数，其中 m ) 2 石1 霸+ 妻v 2 ( x + 1 ) z 1 ， ( 3 - 1 - 1 ) z 是正整数 下面我们给出四个图玩n t o ( 2 n ，n ) ，- 6 ，- 8 ，如图3 1 所示 啭卜卜虹吹 巩n ，nt o ( 2 n ，佗) - 6- 图孓1 图u 2 n ，n ；图t o ( 2 n ，n ) ；图风；图风 一1 7 硕士学位论文 引理3 1 4 ( 3 9 】) 设树具有完美匹配的s 阶树( s = 2 n ) ，则冗( t ) ( 2 n ，几) 等号成立当且仅当t 竺t o ( 2 n ，死) ，其中 帅川= 等等+ 赢南+ 鲁 设g 铭，n = g ：g 是具有最大匹配数为n 且s 个顶点的单圈图) 显然锡n n 表示具有完美匹配的2 n 个顶点单圈图的集合 引理3 1 5 ( 【4 0 】) 设图g 锡叩 风，日8 ) ，礼2 则r ( g ) 矽( 2 礼，n ) 等 号成立当且仅当g 垡巩n 朋其中 蜘，= 若崭+ 南+ 砺n + 学 注：由文献 4 0 】可知，r ( 风) = 2 7 3 2 1 1 妒( n ，七) 1 8 具有完美匹配的仙人掌图的谱半径及其r a n d i d 指数下界 证明 妒( n - 1 , k ) 一妒( 佗，七) + 丽2 + 丽1 一丢 扎+ k 一2 1扎+ k 一1 1 2225千葡十了磊亏青一v2cn+k)一j-i+kx2(-k k1 +一1 ) 。、n + 一 211 1 + 丽+ 丽一砺一互 = i ( n + k - 2 ) 一，( n + 七一1 ) + 丽2 + 丽1 一砺1 一三 伴) 一邢) + 丽2 + 丽1 一砺1 一三 ( 由引理3 1 3 5 而+ 孺一面一丽+ 丽+ 万一砺一2 同时有 妒( n 一1 ，七) 一妒( n ，七) + 击+ 1 妒( n 一1 ，七) 一妒( n ，) + 击+ 去一 0 从而引理得证。 一1 9 - 硕士学位论文 3 2 够( n ，k ) 中r a n d i d 指数的下界 在本节中，我们证明了具有完美匹配的仙人掌图r a n d i 6 指数的下界 定理3 2 1 设图g 够( 竹，k ) 风，日8 ，n 2 则r ( g ) 妒( 礼，k ) 等号成 立当且仅当g 竺a ( n ，七，o ) 证明我们对几和k 归纳证明当k = 0 或k = 1 时，由引理3 1 4 和引 理3 1 5 ，定理显然成立 当n = 3 时，则对于g 够( 3 ，k ) 的圈数k 2 ，其中当死= 3 ，k = 2 时，在 够( 3 ，2 ) 中仅存在四个图，如图3 - 2 所示，我们可证得在够( 3 ，2 ) 中o ( 3 ，2 ，0 ) 有 最小的r a n d i d 指数，定理成立 设m 是图g 箩( 礼，k ) 的一个完美匹配下面我们对死4 且k 2 的 情形进行证明： 2 7 1 2 1 陟司 图3 - 2 够( 3 ，2 ) 中四个图及其r a n d i d 指数 2 9 1 4 2 情形16 ( a ) 2 如果g 够( n ，尼) ，那么g 中顶点秽的度数d ( v ) 礼+ k ，等号成立当且 仅当顶点t ，是图g ( n ，k ，0 ) 中所有圈相交的公共点 由仙人掌图定义知，图g 每个块是圈或为边，则在此情形下，在图g 中必至少存在一个圈c = u l u 2 u t u l 满足2 d ( u 1 ) = d n + k 和d 他) = 2 2 0 具有完美匹配的仙人掌图的谱半径及其r a n d i 6 指数下界 ( i = 2 ，) 设n ( u 1 ) = 砌，饥，z 1 ，x 2 ，x d 一2 ) 显然，边u l u 2 和边钉1 不 能同时属于m ，不妨设u l u 2 隹m 令g2g 心1 u 2 j j l ug 够( n ，k 一1 ) t 月6 ，日8 ，- 由归纲1 阪1 芟，r ( g 7 ) 妒( 几，七一1 ) r ( g ) = r ( g ，) + 面1 + ( 丽1 一志) 霎志+ 互1 一砺1 p ( n , k - 1 ) + 面1 + ( 丽1 一而与) 霎而1 + 互1 一砺1 = 咖+ 端+ 而毛一而n + k 丽- 1 一丽1 + 面1 + ( 刁1 一志) d - 1 志 咖+ 高褊+ 南一而n + k 而- 1 一丽1 1 ，1 1 、d 一1 + 了；芴+ ( 丽一了再三彳) _ 7 r = 咖”一击) ( 高一丽1 ) + 亟# 芦 瓶一、蕊 v 2 咖，卅( 1 一去) ( 志一志) + 、n + k 刁- l _ - v - f f + k 丽一诉再百j v 2 = 咖，卅( 1 一去) ( 南一志) 情形26 ( g ) = 1 我们对情形2 分两个子情形进行证明： 子情形1 至少存在一个悬挂点与一个2 度点u 相邻 设点伽为点u 的另一邻点，则u 叫e ( g ) ，i n ( w ) np v i = 7 1 ，d ( t i j ) = - 2 1 - 硕士学位论文 d n + k ，d ( x 1 ) = d ( x 2 ) = = d ( x r ) = 1 ，n ( w ) p v = x r + 1 ，x r + 2 ，z d 一1 ，z d = t i ) 且d ( 巧) = d j 2 令g ，= g t 一口，则g ，够( 死一1 ，七) 风，风 由归纳假设，兄( g ，) p ( n 一1 ，七) r ( a ) = 卿r 刁1 一丽1 ) + 丽1 一丽1 ) ；萎d - 1 。丽1 + 砺+ 雨 彬) t r ( 击一击) + ( d 一) 面1 一了南) 11 fi ，一 、2、2 d 妒( n - 1 , k ) 州击一志) + ( d 一，- 1 ) 而1 一丽南) 11 + _ = + _ = 4 22 d = 州) + 端+ 而斋+ 号+ 学 礼+ 七一11n 一1 ( 1 一、2 ) 忌。1 1 y 2 ( n + k ) v f n - 干k 以 2 。讵。伺 + r ( 击一击) 州一，_ 1 ) 面1 一而南) = 咖+ 端+ 而吾一而n + k 丽- 1 一丽1 + 去州击一击d - r - 1 ) ( - - 去2 d 一南， 由引理3 1 2 知，1 若，= 0 ，则由上述( 3 2 2 ) 式有： 即) 咖+ 端+ 而丢一了n 丽+ k - 1 一丽1 + 去州叫c 去一丽南， 一2 2 具有完美匹配的仙人掌图的谱半径及其r a n d i 6 指数下界 = p ( n ，k ) 4 - f ( n4 - 七一2 ) 一，( 他+ k 一1 ) 】一【，( d 一2 ) 一，( d 一1 ) 】 + ( 击- 1 ) 刁1 一了霸1 ) 妒( n ，尼) ( 由弓i 理3 1 3 ) 看r = 1 ，则宙上述( 3 2 2 ) 式有： 即) 咖+ 高褊+ 而杀一而n + k 丽- 1 一焘 + 而1 + 丽1 一志+ ( d 2 ) ( 去一而南+ 了；萄+ 丽一了i 三彳+ ( d 一2 ) ( 了；覆一了乏丽) = 咖+ 意褊+ 而丢一了n 丽+ k - 1 一丽1 d 11d 2 1 伺瓶钜研而 = 妒( n ，k ) + f ( n + k 一2 ) 一，( n + k 一1 ) 】一l 厂( d 一2 ) 一，( d 一1 ) 】 妒( n ，k ) “扫弓i 理3 1 3 1 等式r ( g ) = 妒( 死，k ) 成立当且仅当上述所有不等式中等号成立，即 r ( g ，) = 妒( 竹一1 ，七