（基础数学专业论文）某些给定顶点数和围长的三圈图的谱半径.pdf

兰州大学2 0 1 0 届硕士学位论文 摘要 我们称g 是三圈图，如果g 满足i e ( g ) i = i y ( g ) i + 2 设t 为一个三圈图t 的基图 是指t 的极小三圈子图三圈图有七种类型的基图，我们记为：互，其中i = 1 ，2 ，7 设正( n ，9 ) 是顶点数为礼围长为g 且基图为互( 其中i = 1 ，2 ，7 ) 的所有三圈图的集合 本篇论文中，我们分别找出了图集互( 礼，9 ) ( 其中i = 1 ，2 ，3 ，4 ) 中谱半径最大的图同 时，我们也确定了图集u 叁】互( n ，9 ) 中谱半径最大的图更进一步的，我们证明了最大谱 半径是围长9 的减函数 关键词：三圈图；围长；基图；谱半径 i 兰州大学2 0 1 0 届硕士学位论文 a b s t r a c t f o rat r i c y c l i cg r a p ht t h eb a s eo fti st h em i n i m a lt r i c y c l i cs u b g r a p ho ft t h e r e a r es e v e nt y p e so fb a s e sf o rt r i c y c l i cg r a p h s ，s a y , 互，i = 1 ，2 ，7 l e t 互( n ，g ) b et h es e t o fa l lt r i c y c l i cg r 印h so nnv e r t i c e sw i t h 舀r t hgh a v i n gt h eb a s eo ft y p e 互，i = 1 ，2 ，7 i nt h i sp a p e r ，w ed e t e r m i n et h eu n i q u eg r a p hw i t ht h el a r g e s ts p e c t r a lr a d i u sa m o n ga l lt h e g r a p h si n 互n ，g ) f o ri = 1 ，2 ，3 ，4 w ea l s od e t e r m i n et h eu n i q u eg r a p hw i t ht h el a r g e s t s p e c t r a lr a d i u sa m o n ga l lt h eg r a p h si nu 冬1 磊( 礼，9 ) m o r e o v e r ，t h el a r g e s ts p e c t r a lr a d i ia r e d e c r e a s i n gf u n c t i o n so ng k e yw o r d s ：t r i c y c l i cg r a p h ；g i r t h ；b a s e ；s p e c t r a lr a d i u s i i 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进行研 究所取得的成果。学位论文中凡引用他人已经发表或未发表的成果、数据、 观点等，均已明确注明出处。除文中已经注明引用的内容外，不包含任何其 他个人或集体已经发表或撰写过的科研成果。对本文的研究成果做出重要贡 献的个人和集体，均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：亟銎垒日期：兰! l 垫鱼鱼! 马 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属兰州 大学。本人完全了解兰州大学有关保存、使用学位论文的规定，同意学校保 存或向国家有关部门或机构送交论文的纸质版和电子版，允许论文被查阅和 借阅；本人授权兰州大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用任何复制手段保存和汇编本学位论文。本人离校后发 表、使用学位论文或与该论文直接相关的学术论文或成果时，第一署名单位 仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：煦导师签名：癖日期：赳 己i吉 ji 目 图论在自身发展的过程中，开始呈现出与数学其他分支相融合的特点新的数学分 支也不断诞生代数图论就是其中之一，它是代数与图论相结合的产物，其实质是将图 论上的一些问题用代数的方法来解决图谱理论是代数图论中开始较早，且重要性较强 的研究方向图谱理论最初是被物理学家和理论化学家作为离散的数学方法用于求解一 类偏微分方程的近似解随后，其在物理学家、理论化学家、数学家的共同努力下得到 了飞速发展至今，经不断积累和完善，图谱理论已经成为许多专业学习的必备知识图 的各种谱为图谱理论的核心内容在这门理论中，我们引入了图的邻接矩阵，拉普拉斯 矩阵等来研究图的性质，这几种矩阵与图都有着自然的联系，他们的特征值对应于图的 不同的谱 图的邻接矩阵的谱( 简称邻接谱) 为最早被研究的谱其起源于量子化学领域1 9 3 1 年， e h i i c k e l 在对非饱和碳氢化合物的研究中，引入了一种近似处理，从而得到对应分子的 图论模型此种模型中，特定电子的能量级用图的特征值来表示此后，图的邻接谱得到 了众多化学家和数学家的研究和应用如今，图的谱理论还包含许多关于网络物理性质 的好结果，如图的直径，连通性，图的相关矩阵的特征值 3 1 1 2 4 等等通过文章 2 4 ，我们 知道图的谱半径( 即：图的邻接矩阵的最大特征值) 在模拟网络病毒传播中起到了重要 的作用图的谱理论在化学中的应用也非常的广泛 图的谱半径的研究已经成为图的谱理论中的一个重要研究领域b r u a l d i ，s o l h e i d 【1 】 提出了一个重要研究课题：设s 为一个给定的集合，在s 中寻找一个潜半径的上界，并将 达到这个上界的图刻画出来经过许多中外学者的不懈努力，此问题取得了一系列进 展在文章【2 】中，b e r m a n 和z h a n g 在所有具有相同顶点数和割点数的连通图中，找到了 谱半径最大的图h a n s e n 和s t e v a n o v i 6 1 5 】刻画了给定顶点数和直径的所有图中谱半 径最大的图l i u 等 2 3 】研究了给定顶点数与割边数的图的谱半径单圈图的谱半径已 经被很多人研究过 6 1 0 1 1 9 2 8 3 5 1 g u o e t a l f 1 0 1 1 2 5 研究了具有n 个顶点且含有尼个悬挂 点的单圈图和双圈图的谱半径，y u 和t i a n 【3 6 研究了最大匹配为m 的双圈图的谱半径 g u o 【1 2 1 确定了给定顶点数和直径的所有图中谱半径最大的图z h a i 等 3 8 】刻画了给定 顶点数和围长的所有双圈图中谱半径最大的图g e n g 和l i 8 】对给定顶点数和悬挂点数 的所有三圈图的谱半径做了研究最近，还有许多关于谱半径和l a p l a c i a n 谱半径的研究 成果 本文主要研究了一些给定顶点数以及围长的三圈图集合的最大谱半径及极值图本 文共分五章首先，我们将顶点数为礼围长为g 的三圈图集合丁( 佗，g ) 按照其基图的形状 分为七个部分：互( 几，9 ) ，i = 1 ，2 ，7 在第一、二、三、四章中，我们分别刻画了集 1 兰州大学2 0 1 0 届硕十学位论文 合五( 亿，9 ) 、正( 扎，夕) 、死( 礼，夕) 、五( n ，9 ) 中谱半径最大的图，第五章，通过比较上述四类图 集的最大谱半径，我们确定了集合而( n ，9 ) = 五( 礼，9 ) u 正( n ，9 ) u 五( n ，9 ) u 五( n ，夕) 中谱半 径最大的图 2 预备知识 本文考虑的图均为无向、无重边、无自环、有限的简单图设g 为一个图用v ( v 1 表 示图g 的顶点集，e ( g ) 表示g 的边集图g 的顶点 的邻集用g ( u ) 或者n ( v ) 表示顶 点 的度是指与钉关联的边的个数，用d g ( 口) 表示图g 的围kg ( v ) 是指g 中最小圈的长 度通常，我们用r 表示礼阶路，用g 表示n 阶圈设岛是通过在一个给定的顶点 上 连接钆一1 条悬挂边得到的图，我们称& 为礼阶星，并称顶点移为& 的中心 设a ( g ) 为图g 的邻接矩阵a ( g ) 的特征多项式用圣( g ，a ) 表示为了方便，文章 中我们经常用g 来表示圣( g ，a ) 显然a ( g ) 为实对称矩阵，并且它的特征值均为实数 图g 的谱半径p ( e ) 为a ( g ) 的最大特征值如果g 是连通的，那么a ( g ) 为非负不可约矩 阵由p e r r m f r o b e n i u s 定理 2 0 1 ，我们知道，谱半径p ( a ) 是单的，并且有唯一的一个正 单位向量对应于p ( a ) ，我们称这个向量为g 的尸e r r 帆向量用l z l 表示小于等于z 的最 大整数用x 表示大于等于x 的最小整数 我们称g 是单圈图，如果g 满足i e ( g ) i = l y ( g ) l ；称g 是双幽图，如果g 满足l e ( g ) l = i y ( g ) l + 1 ；称g 是三圈图，如果g 满足l e ( g ) i = i y ( g ) i + 2 用丁( 礼，g ) 表示顶点数为n 围 长为g 的所有三圈图的集合对于个三圈图t 来说，t 的基图为其极小j 圈子图，我 们用一来表示显然，一是t 的唯一一个不包含悬挂点的三圈子图，并且t 可以通过 在p 上连接一些树得到 由【2 2 】，我们知道，如果g 为三圈图，那么它至少包含三个圈，至多包含七个圈，但是 不会包含五个圈根据( 8 三圈图的基图共有七种类型，我们用五，i = 1 ，2 ，7 表示， 见图1 我们用磊( n ，g ) 表示顶点数为礼围长为g 且以磊为基图的所有三圈图的集合，其中i = 1 ，2 ，7 本文我们主要研究以互，i = 1 ，2 ，3 ，4 为基图的三圈图，并令而( n ，g ) = 五( 钆，g ) u 乃( n ，9 ) u 五( 佗，g ) u 五( n ，夕) 设磁 ，。表示具有公共端点的四条内部两两不交的路昂，蜀，b ，只，并且在其中一 个公共端点上连接k 条悬挂边得到的图( 图2 ) 一个图集中具有极大谱半径的图，简称为该图集的极值图 岛 铲2 g 1 火 () g 。 3 正( 呦伽) 兰州大学2 0 1 0 届硕士学位论文 善葶一旬 0 磊 图1 三圈图的七类基图 昂 昂 只 昴 图2 三圈图磁q r 8 所有在本文中出现的未定义的符号，或图论的术语，请读者参照文献 3 】和 9 】 4 7 一 芝只分芝 第一章 正( n ，g ) 中的极值图 本章中，我们将刻画图集五( n ，g ) 中谱半径最大的图。首先我们给出几个引理： 引理1 1 ( 【3 2 】) 设g 为连通图，p ( g ) 是a ( g ) 的谱半径设u ，u 为图g 的两个顶点， v d i = 1 ，2 ，s 】n c ( v ) n o ( u ) ( 1 8 d g ( ) ) ，并且x = ( x l ，x 2 ，z 竹) t 为图g 的p e r r 帆向量，其中x i 对应于顶点v i ( 1 t 礼) 设g + = g e 釜1 仇移+ e 釜1v i u 如 果z u z ，习肛么p ( g ) p ( c + ) 设g ，日为两个不相交的连通图，其中u v ( v ) ，w y ( 日) 用g u w h 表示将让和w 捏成一个顶点所成的图图3 中的g u v t k 和g u w s k 分别为图g 和图死以及图g 和鼠通 过上述方式形成的图 g u v t kg u w s k 图3 图g u v t k 和g u w s k k 1 推论1 2 ( 3 2 1 ) 设g 为非平凡的连通图，死为顶点数是k 的树，& 为中心为w ，顶点 数为k 的星那么，对于任意的乱v ( g ) 以及 v ( t k ) ，总有p ( g u v t k ) p ( g u w s k ) 等 号成立当且仅当g u v t 七竺g u w s k 设g 为连通图，并且u v e ( g ) 用g “ 表示通过细分图g 的边伽得到的图，即通过 在图g u u 中添加一个顶点w 和两条边w u ，w v 得到的图图g 的内部路是指满足下列 条件的顶点序列i l l v 2 v k ( k 2 ) ： ( i ) 序列中顶点各不相同( v 1 = v k 是可能的) ； ( i i ) v i 与v i + 1 邻接( i = 1 ，2 ，k 1 ) ； ( 捌) 顶点度满足d a ( v 1 ) 3 ，d g ( v 2 ) = = d e ( v 南一1 ) = 2 ( 除非k = 2 ) ，d c ( v k ) 3 用w n ( n 6 ) 表示在路v l 秽2 一4 的顶点u 1 和一4 上分别连接两条边得到的图 引理1 3 ( 1 2 1 ) 设g 为连通图。如果u 口为图g 的内部路上的一条边，并且g 喾眠， 那么p ( g 伽) p ( g ) 引理1 4 设g 1 和g 2 为两个图 ( i ) ( i t 7 ) 如果g 2 为连通图g 1 的一个真子图，那么p ( g 2 ) 圣( g 1 ，a ) ，那么p ( g 2 ) p ( v 1 ) 下面我们给出极值图的一些性质： 引理1 5 设t 为图集互( n ，夕) ( z = 1 ，2 ，7 ) 中具有极大谱半径的图，p 为图t 的基 图则 5 兰州大学2 0 1 0 届硕+ 学位论文 ( i ) 图t 的所有不在顶点集y ( p ) 中的顶点是悬挂点； ( i i ) 所有t 的悬挂点( 如果存在的话) 都连接在一的唯一一个顶点矿上，我们称这个 顶点为星根 证明( i ) 由基图的定义，我i r i s h 道图t 可以通过在p 的某个顶点上连接一些树得到 因为t 为极值图，那么由推论1 2 ，这些树一定是星因此t 的所有不在顶点集y ( p ) 中 的点都为悬挂点 ( i i ) 用x = ( z 1 ，z 2 ，z n ) 表示图t 的p e r 7 帆向量设为图t 的所有悬挂点的集 合，并且u v 。n ( v ) = 【u 1 2 ) 假设8 2 不失一般性，设z 口。= m a x z 仇1 1 i s _ 并且v nn ( v 2 ) 那么，由引理1 1 p ( t 1 p ( t v v 2 + v v x ) 显然t v v 2 + v v l 是一个三圈图，并且与t 有相同的基图，矛盾因此8 = 1 ，( i i ) 成立 用霹云笋+ 2 表示图4 中的图，那么露鲫- 3 9 + 2 五( 亿，9 ) 接卜来，我们给出本章的主要结果： 定理1 6 设t 五( n ，夕) 则p ( t ) p l t 工g ，n 鲫- 3 9 + 2 ) ，等式成立当且仅当t 垡，n ，五笋+ 2 更 进一步的，p t q n - 3 9 + 2 ) 是g 上的递减函数 证明设t 为图集五( n ，g ) 中具有极大谱半径的图，并且p 为t 的基图那么，对 于2 1 ，1 2 ，z 3 1 ，s 1 g 以及s 2 g ，有p = 五( 见图1 ) 由引理1 5 ，图t 的所有不在顶点 集v ( t o ) 中的顶点都为悬挂点，并且这些点都连接在基图t o 的唯一一个顶点u + 上 首先，我们证明2 1 = 2 2 = f 3 = 1 相反的，我们假设1 1 2 和昂。= v l v 2 饥。，其 中饥，y ( g ) ( 见图1 ) 设x = ( x l ，x 2 ，z n ) 为乃的p e r r o n 向量如果z 口。z ，那么 由引理1 1 ， j 口( t ) p ( t 一口耽。+ 批) ， v e v ( c 9 ) n n ( v t l )v e v ( c o ) n n ( v t l ) 显然，不等式右边的图在图集五( n ，g ) 中，矛盾如果z 移， z ，那么由引理1 1 ，有 p ( t ) p ( g k ，m ) ，总有： 西( g 知+ 1 , m - - 1 ，a ) 圣( g 七m ，入) 定义西( p - 1 ，入) = o 以及垂( 岛，a ) = 1 那么由引理2 2 ，对于任意的礼1 ， 圣( f k ，a ) = 入圣( 户k 一1 ，a ) 一圣( f k 一2 ，a ) 设屏，”b p t ( a 6 ) ( 1 2 ) 以及磋伽( n ，6 ) 分别表示图6 中所示的图，其中u o 和v o 分 圈g 为两条路r 和r ，a + b = r 十2 ，a ，b 2 用g ( 忌，m ) 表示通过在圈g 的某个顶 8 兰州大学2 0 1 0 届硕士学位论文 点上连接长度分别为k 和m 的两条不交路得到的图由引理2 2 可以得到： 圣( j e i 品( n ，6 ) ，入) = a 圣( 睇p ，l ，( o ，6 ) - - u ，入) 一西( b 昌( o ，6 ) 一珏一口，a ) t ，( t ) 因此， 硌( 口，6 ) = 入岛，只一2 一昂，r 蜀一3 一c p ( a - 1 ，6 1 ) p l 一2 = 邱，只一1 一q ( o l ，6 1 ) 只一2 ( 3 ) 邱r n t 6 b p 门髟p ，i ，( o ，6 ) 和磋咖( n ，6 ) 令耳，伽( n ，6 ) = 磋伽( o ，6 ) 我们有： 引理2 5 对于任意的k 0 ，罐伽( 口，6 ) = a 七耳，r i q ( o ，6 ) 一k a 詹c p ( a 一1 ，b 一1 ) 岛一1 成 证明：显然， 磋r i g ( o ，6 ) = 耳 。( o ，6 ) 以及磋伽( n ，6 ) = a 昂朋a ，6 ) 一q ( o 一1 ，b 一1 ) 局- 1 对k 用归纳法，假设结论对k 成立，那么由引理2 2 ，可以得到 t p k + ，。l ( a ，6 ) = a 磋，g ( o ，6 ) 一a * c p ( a 一1 ，b 一1 ) p q 一1 = a ( a 七易，r i 口a 6 ) 一k a 七一1 岛a 一1 ，b 一1 ) 局一1 ) 一a k c p ( a 一1 ，b 1 ) 蜀一1 = 入七+ 1 耳 r 口( n ，6 ) 一( 七+ 1 ) a 惫c p ( n 一1 ，b 一1 ) 蜀一1 因此结论成立 引理2 6 如果a p ( q ( o 一1 ，b 一1 ) ) ，那么对于任意的a b 3 以及k 0 ， 磋咖( n ，6 ) t ”k ，口a + 1 ，b 一1 ) 成立 证明： 在图磋r i q ( o ，6 ) 中，令口n ( v o ) nv ( c o 那么由引理2 2 和( 3 ) ，我们有： = 入b 耋 1 ( n ，6 ) 一b ；52 ( n ，6 ) 一c p ( a 一1 ，b 一1 ) 岛一2 2 c a a 一1 ，b 一1 ) = b 易( o ，6 ) 一g r p ( o 一1 ，b 一1 ) p q 一2 2 c p ( a 一1 ，b 一1 ) = 讳，p g 一1 一q ( n 一1 ，b 一1 ) p q 一2 一q ( 口一1 ，b 1 ) p g 一2 2 q ( o 一1 ，b 1 ) = b p ，r 岛一1 一( 2 岛一2 + 2 ) g ( 口一1 ，b 一1 ) 9 兰州大学2 0 1 0 届硕士学位论文 由引理2 5 和引理2 4 ，我们可以得到 磋r ，q ( n ，6 ) 一v 上p p k ，+ r q l t o + 1 ，b 一1 ) = a 七弓，r ，q ( n ，6 ) 一k a 七一1 c p ( o 一1 ，b 一1 ) p q 一1 一( 入七昂，r ，g ( n + 1 ，b 一1 ) 一k a 七一1 c pa ，b 一2 ) 局一1 ) = 入南( 耳，r ，口( o 6 ) 一耳，r ，口( n + 1 ，b 一1 ) ) + k a 七一1 局一l ( c p ( o ，b 一2 ) 一ga 一1 ，b 一1 ) ) = 舻 岛，r b 一1 一( 2 岛一2 + 2 ) qa 一1 ，b 一1 ) 一( 岛，马一1 一( 2 岛一2 + 2 ) q ( o ，b 一2 ) ) 】 + 后a 七一1 局一1 ( c ；( o ，b 一2 ) 一c l p ( n 一1 ，b 一1 ) ) = 入七( 2 岛一2 + 2 ) ( c 刍( o ，b 一2 ) 一c p ( o 一1 ，b 1 ) ) + k a 七一1 p q 一1 ( c 刍( n ，b 一2 ) 一c p ( o 一1 ，b 一1 ) ) = 附( 2 岛一2 + 2 ) + k a 扣1 局一1 】( ( o ，b 一2 ) 一qa 一1 ，b 1 ) ) n 现在，我们给出本章主要的结果： 定理2 7 设t 乃( n ，9 ) 则p ( t ) p ( 瑁9 l g - 3 9 + 2 ( 9 ，2 ) ) ，并且等式成立当且仅当t 竺 霹i 笋+ 2 ( 9 ，2 ) 更进一步的，n p t n 夕9 - 3 9 + 2 ( 夕，2 ) ) 是g 上的减函数 证明： 设t 为图集正( 礼，g ) 中具有极大谱半径的图类似于定理1 6 的讨论，我们 可以证明t = 冠g - ，3 。g 十2 ( o ，b ) 对于某个正整数n ，b 2 成立，其中o + b = g + 2 我们证 明o = 2 或者b = 2 利用反正法，假设n b 3 因为q 一1 ，1 ) 是露五泸+ 2 ( 9 ，2 ) 的一个 真子图，那么，对于a n p ( t 上夕 n 鲫- 3 9 + 2 ( 夕，2 ) ) ，a p ( 岛国一1 ，1 ) ) 成立因此，由引理2 6 可得 z 蛩g - ，9 3 9 + 2 ( n ，6 ) 7 蛩五9 3 9 + 2 ( o + 1 ，b 一1 ) 7 爱9 - ，9 3 9 + 2 ( 夕，2 ) 而由引理1 4 ( i i ) ，我们知道i j i ，, 删l g , g 一, 3 9 9 十2 ( n ，6 ) ) q ，那么： ( i ) 对于任意的p ，q 2 和t 0 ，昂一1 ，口一2 ，t + l + 耳一2 旷1 ，汁1 一耳一1 口一1 ，t 0 成立 ( i i ) 对于任意的o b 2 和k 1 ，磁口a ，b ) 磴q ( n + 1 ，b 一1 ) 成立 ( i i i ) 对于任意的a b 2 ，u p ，g ( o ，b 一2 ) u p ，q ( n 一1 ，b 一1 ) 成立 引理3 2 ( 【3 8 ) 对于任意的k 1 ，p ( 磴口，r ) q ，其中q 是等式z l 5 一x 一1 = 0 的实根 磷惑 图7 p p k , 口c 8 n 6 ) ，磋黪和确( o ，6 ) 用磋乒( n ，6 ) ，磋 , c s 和躜( o ，6 ) 分别表示图7 中的三个图那么，当n = 1 或6 = 1 时， 磋精= 磁乒( o ，6 ) ，其中r = a + b 一1 设确( o ，6 ) = 磋乒( o ，6 ) 取 ( u o ) ny ( 蜀) 那 么由引理2 2 ，我们可以得到： 即 巧p ，。l ( o ，6 ) = a ( 确( o ，6 ) 一钉) 一( 唆( o ，6 ) 一 一乱) u e n ( v ) = a p ( p ，q ，r ) 蜀一2 一p ，q ，r ) 毋一3 一u p ，q ( n 一1 ，b 一1 ) 只一2 弓p ，口l ( o ，6 ) = p ( p ，q ，7 ) 毋一1 一u p ，g ( o 一1 ，b 一1 ) 最一2 1 1 兰州大学2 0 1 0 届硕士学位论文 引理3 3 ( i ) 对于任意的七0 ，f p p q p k , c n ，6 ) = a 七确( o ，6 ) 一k a 七一1 q ( o 一1 ，b 一1 ) p 8 1 成立 ( i i ) 对于任意的k 0 ，p ( 磋知) q 成立，其中q 是方程z 1 一z 一1 = 0 的实根 证明：( i ) 显然， 磋乒( o ，6 ) = 磁( n ，6 ) 并且磋乒( o ，6 ) = 入确( o 6 ) 一u p ，口( o 一1 ，b 一1 ) p 8 1 我们对k 用归纳法，假设( i ) 对于k 成立由引理2 2 可得 磷亭1 ，g ( n ，6 ) = 入磴乒( n ，6 ) 一a 七，q ( o 一1 ，b 一1 ) p s 一1 = a ( a 七f 翰( o ，6 ) 一k a 七一1 ，口( o 一1 ，b 一1 ) 9 8 1 ) 一入七，ga l ，b 一1 ) p 8 1 = 入七+ 1 f 易( n ，6 ) 一( 后+ 1 ) 入七，口( o 一1 ，b 一1 ) p 8 1 因此( i ) 成立 ( i i ) 由于对于任意的k 0 ，磋q ，总是磋知的一个真子图那么由引理1 4 ( i ) 和引 理3 2 可得p ( 7 1 ”- p 凫, q d , r ) 、 p ( e l ) o t 引理3 4 设口是方程z 1 5 一z 一1 ：0 的实根如果a q ，那么对于任意的a b 2 以 及七0 ，磴乒a ) 磋乒( n + 1 ，b 一1 ) 成立 证明： 在图磴乒( o ，6 ) 中取 ( u o ) ny ( g ) ，那么由引理由引理2 2 和( 4 ) ，我们可 得到： 磁( o 6 ) = a ( 磁( o ，6 ) 一t ，) 一( 确( o ，6 ) 一 一u ) 一2 ( 磁a ，6 ) 一y ( g ) ) u e n ( v )c e c ( v ) = 入f 舄一1a ，6 ) 一f 易一2 ( o ，6 ) 一，g ( o 一1 ，b 一1 ) 只一2 2 ，q ( o 一1 ，b 一1 ) = 磁a ，b ) 一( 只一2 + 2 ) ，口( o 一1 ，b 一1 ) = p p ，口，7 ) 只一1 一，g ( o 一1 ，b 一1 ) 只一2 一( 尸s 一2 + 2 ) ，q ( n 一1 ，b 一1 ) = p ，g ，r ) 只一1 一( 2 只一2 + 2 ) ，ga 一1 ，b 一1 ) 1 2 兰州大学2 0 1 0 届硕士学位论文 由引理3 3 和引理3 1 ，我们司得到： 磴乒8 ( o ，b ) 一磺f 8 ( n + 1 ，b 一1 ) = a 七置蠹( o ，6 ) 一k a 七一1 ，q ( o 一1 ，b 一1 ) 只一1 一( 入k f 舄( n + 1 ，b 一1 ) 一七入七一1 ，口( n ，b 一2 ) 只一1 ) = a 七( z ( o ，6 ) 一只( o + 1 ，6 1 ) ) + k a 七一1 只一1 ( u p ，口( o ，b 一2 ) 一，口( n 一1 ，b 1 ) ) = 入k 【p ，q ，7 ) p 8 1 一( 2 只一2 + 2 ) ，口( o 一1 ，b 一1 ) 一( p ( p ，q ，7 ) 只一1 一( 2 只一2 + 2 ) ，口( n ，b 一2 ) ) 】+ k a 扣1 只一1 ( ，g ( n ，b 一2 ) 一，q ( o ，b 一2 ) ) = 入危( 2 p 8 2 + 2 ) ( ，口( o ，b 一2 ) 一，q ( n 一1 ，b 一1 ) ) + k a 七一1 只一1 ( ，口( o ，b 一2 ) 一，口( o 一1 ，b 一1 ) ) = 盼七( 2 p s 一2 + 2 ) + k a k 一1 只一1 】( ，口( n ，b 一2 ) 一，qa 一1 ，b 一1 ) ) n 定理3 5 设t 死( n ，9 ) 则p ( t ) 烈- r - 咝- r - 警1f 芷亨：碰i ) ，等式成立当且仅当t 竺 _ p r , , - r 譬1 蒙+ 3 , c ，9 t 豁署蒸豢ng ：；裱飘凌篙嚣的基图那么对于某证明：设t 为图集瓦，) 巾的具有极大谱半径的图，p 为t 的基图那么对于某 个t 1 ，s g 以及适当的整数p ，q ，a ，b ，有p = 磊( 见图1 ) 与定理1 6 的证明类似，我们 可以得到t = 1 ，s = 夕，并且可以找到适当的整数p ，q ，o ，b 以及k ，使得t = 壤尹9 ( n ，6 ) 首先我, f m j i 正明t = p ，k ，静( 即磋c g ( 7 ，1 ) ) ，其中p ，q ，r ，七为整数，且r = n + b 一1 ，即口= 1 或者b = 1 相反的，假设n b 2 那么对于入p ( 磋黪) ，由引理3 3 ，我, i l i o n 道入 0 c 因此，由引理3 4 ，可得 磋p ( 。，6 ) 磋乒( o + 1 ，b 一1 ) 磋乒( n1 ) = 磋， 再由引理1 4 ( i i ) 可以得到p ( 磋乒a ，6 ) ) 烈 ，n p k 胁, c ，g ，矛盾因此t = 磋q , r 不失一般性， 假设p q r 如果p q ，那么p p k 一+ 1 l ，q ，r , c 9 与p p p k 胁, c r 9 的围长相同，并且置雾乃( 扎，9 ) 由引理1 4 ( i ) 和引理1 3 可得： p ( 磋移) p ( 磁筘q ) a 0 6 7 5 西( r 一1 ，a ) 0 成立 证明：显然，西( p 1 ，a ) = a a o 6 7 5 圣( 昂，入) = 一6 7 5 0 由归纳法以及( 2 ) ，我们可以 得到 垂( r ，入) 一) 0 6 7 5 圣( r 一1 ，入) = 入垂( r 一1 ，入) 一西( r 一2 ，入) 一a 0 6 7 5 圣( r 一1 ，入) = ( a a o 6 7 5 ) m ( r 一1 ，a ) 一中( r 一2 ，a ) ( 入一a 0 6 7 5 ) 入o 6 7 5 1 】圣( r 一2 ，入) ( p 1 6 7 5 一p 1 3 5 1 ) 西( r 一2 ，入) = 0 用磁 a 6 ) ( 图8 ) 表示具有公共端点的四条内部两两不交的路b ，岛，b ，p 8 ，且在路 只的某个的顶点乱4 上添加k 条悬挂边形成的图，其中n + b = s + 1 ，札+ 分路只成r 和昂 显然，p 剐o ，r ( n ，6 ) 竺p ( p ，q ，r ，s ) ，并且，当o = 1 或者6 = 1 时，p 舢k ，( o ，6 ) 竺p p q k 。，其中s = o + b 一1 由引理1 5 ，可得五( n ，9 ) 的极值图同构于磁g ，( o ，6 ) ，其中p ，q ，r ，o ，b ，k 为整数 只 口，r ( n 一1 ，b 一1 ) 图8 p 舢k ，r ( o ，6 ) 和 g r ( o 一1 ，b 一1 ) r 一1 用u p ，q r ( o 一1 ，b 一1 ) ( 见图8 ) 表示通过删除磺口，( o ，b ) 中的所有悬挂点以及它们的公 共邻点矿得到的图显然，当b = 1 时， ( o 一1 ，b 一1 ) = 昂一1 ，口一1 ，一1 ，口一1 引理4 2 ( i ) 对于任意的k 0 ，磴 ( o ，6 ) = 舻p ( p ，g ，r ，o4 - b 一1 ) 一从k - 1 u p ，口，( o 一 1 ，b 一1 ) 成立 ( i i ) 对于任意的k 1 ，p ( 磁q r ，。) p 成立其中p 是方程z 1 肼5 一z 1 册一1 = 0 的实 根 1 5 兰州大学2 0 1 0 届硕十学位论文 证明：( i ) 显然， 磋 ( o ，b ) = p ( v ，口，o + b 一1 ) 以及 l 口，( n ，b ) = a p ( p ，q ，r ，o + b 一1 ) 一u p ，q ，r ( n 一1 ，b 一1 ) 通过对k 用归纳法，以及( 2 ) ，可得 q k ，+ q ，八l ，6 ) = a 磁q ，ra ，6 ) 一入七，q r ( o 一1 ，b 一1 ) = a ( 入七p ( p ，q ，r ，o + b 1 ) 一忌入七一1 u p q r ( o 一1 ，b 一1 ) ) 一入七u p q ，( o 一1 ，b 一1 ) = a k + 1 p ( p ，口，nn + b 一1 ) 一k a 七u p ，q ，a 一1 ，b 一1 ) 一入七u p ，g ra 一1 ，b 一1 ) = a k + 1 p ( p ，口，n o + b 一1 ) 一( k + 1 ) a 七u p ，q ，( n 一1 ，b 一1 ) ( i i ) 因为p 2 3 3 7 6 并且k 1 ，所以p ，q ，r ，s 2 ，并且p ，q ，n8 中最多有一个等于2 下边分两科，情形考虑： 情形1 p ，q ，? ，s 3 如果p ，g ， ，s 中至少有两个大于等于4 ，那么互9 ，5 ) 是p m k r 。的真 子图由引理1 4 ( 0 及引理2 3 ，可得： p ( 磁叭。) p ( 丑9 ，5 ) ) = 2 3 7 6 1 口 如果p ，q ，r ，s 中最多有一个大于等于4 ，那么p 3 ，3 ，3 ( 见图9 ) 是p 舢k 。的真子图另一方面， 我们可计算得圣( p 3 ，3 ，3 ，a ) = 入3 ( a 2 6 ) ，从而p ( p 3 ，3 ，3 ) 2 4 4 9 5 再由引理1 4 ( i ) 可得： p ( 磁 ，。) p ( p 3 3 3 ) 2 4 4 9 5 p 情形2 p ，q ，ns 中恰好有一个等于2 ，不妨设p = 2 如果g ，ns 4 ，那么t ( o ，5 ) ( 见 图5 ) 是磁 ，。的一个真子图，因此j 9 ( 磴 ，。) p ( 丑9 ，5 ) ) p 如果g ，r ，s 中最多有两个大 于等于4 ，那么观( 见图9 ) 是磁口，r ，。的真子图，由【3 8 及引理1 4 ( i ) 可得j 9 ( 磴q 。) p ( u 3 ) 2 3 4 2 9 口 图9 p p q k ”的两个子图 昆，3 ，3 引理4 3 设p 是方程z 1 6 7 5 一x 1 3 5 一l = 0 的实根如果a 卢，那么，对于任意 的p ，q ，7 - 2 以历乏t 0 ，昂一1 ，口一1 ，r 一2 ，t + l 十昂一1 ，口一2 r 一1 ，t + 1 + 耳一2 ，g 一1 ，r 一1 ，t + 1 2 一1 ，口一1 ，r 一1 ，t 0 成立 1 6 兰州大学2 0 1 0 届硕士学位论文 证明：设 f ( t ，入) = 耳一1 ，q 一1 ，f 一2 ，t + l + 7 一1 ，叮一2 ，r 一1 ，t + l + 耳一2 ，口一1 ，一1 ，t + l 一2 一1 ，q 一1 ，t 一1 ，t ( i ) 如果p ，g ，r 中有一个，不妨设r ，等于2 ，那么由引理3 1 及引理4 1 ，可得对于任意 的t21 ，总有： f ( t ，入) = 昂一2 岛一2 r + 耳一1 ，g 一2 ，t + l + 耳一2 q - 1 ，t + l 一乃一1 ，q 一1 ，t 0 并且，因为p a 2 1 4 7 9 ，我们可以得到： f ( o ，入) = 昂一2 局一2 + p p + q 一4 + 昂+ q 一4 一昂一2 岛一2 = 2 昂+ q 一4 0 ( i i ) 女n 果p ，g ，r 3 ，那么由( 2 ) 可得： f ( t ，a ) = 入，( t 一1 ，入) 一，( t 一2 ，入) 对于任意的t 2 成立由( 1 ) 以及引理4 1 可得： y ( o ，a ) = t p 一1 ，口一1 r 一2 + 了一1 ，g 一2 ，r 一1 + 7 一2 ，g 一1 ，r 一1 一f 一2 f ；一2 f ； 一2 = a 昂一2 局一2 只一3 一弓一2 局一2 p r 一4 一昂一3 局一2 b 一3 一昂一2 局一3 p t 一3 + a 昂一2 岛一3 p r 一2 一昂一2 岛一4 p r 一2 一昂一3 局一3 p r 一2 一昂一2 岛一a p t 一3 + 入昂一3 岛一2 p r 一2 一昂一4 局一2 p r 一2 一昂一3 局一3 p r 一2 一昂一3 局一2 b 一3 一f ：，一2 b 一2 p r 一2 = 3 p p 一2 岛一2 p r 一2 一昂一2 局一2 只2 2 ( 昂一2 局一3 只一3 + 昂一3 局一2 耳一3 + 昂一3 p q 一3 耳一2 ) = 2 ( 昂一2 局一2 b 一2 一昂一2 局一3 耳一3 一昂一3 岛一2 p r 一3 一昂一3 局一3 p r 一2 ) 2 ( 1 一丽3 ) p p 一2 马一2 b 一2 0 另一方面，由( 1 ) 我们有： ，( 1 ，a ) = z 一1 ，口一1 ，r 一2 ，2 十蜀一1 ，口一2 ，一1 ，2 + 昂一2 ，g 一1 ，r 一1 ，2 一耳一1 ，q 一1 ，r 一1 = 入7 一1 ，q 一1 ，r 一2 一f ；，一2 岛一2 p r 一3 + 入耳一1 ，口一2 r 一1 一f 一2 局一a