（运筹学与控制论专业论文）三圈图的谱半径.pdf

硕士学位论文 m a s t e r st t t e s i s 摘要 图的谱半径是其邻接矩阵的最大特征值由于在图谱理论上的广泛应用，近几 年在这一方面的研究成果如雨后春笋般层出不穷本论文在前人研究的基础上，进 一步研究了三圈图的谱半径主要内容包括： ( i ) 介绍了本文的研究背景和研究意义，国内外在这方面具有代表性的发展状 况通过对本文研究背景及研究现状的深刻讨论，充分说明了本文的主要研 究工作的必要性和创新性最后，给出了本文涉及到的部分记号 ( i i ) 研究了佗个顶点且含k 个悬挂点的三圈图的谱半径问题：确定了具有最大 谱半径的n 个顶点且含k 个悬挂点的三圈图 ( i i i ) 研究了n 个顶点且直径为d 的三圈图的谱半径问题，确定了具有最大谱半 径的扎个顶点且直径为d 的三圈图 ( i v ) 研究了亿个顶点且具有完美匹配的三圈图的谱半径问题，确定了具有最 大谱半径的n 个顶点且具有完美匹配的三圈图 关键词：谱半径；三圈图；悬挂点；直径；完美匹配 a b s t r a c t t h es p e c t r a lr a d i u so fag r a p hi sd e f i n e da 8t h el a r g e s te i g e n v a l u eo fi t sa d j a - c e n c ym a t r i x w i t ht h ew i d e ru s e o fi ti ng r a p hs p e c t r ai nr e c e n ty e a r s ，t h er e s e a r c h c o n c e r n i n ga b o u tt h i sa s p e c th a v em u s h r o o m e dl i k ea ne n d l e s ss t r e a m t h i sp a p e r w h i c hs t a n d so nt h eb a s i so fp r e v i o u sr e s u l t s ，a n dw h i c hf u r t h e rr e s e a r c ho nt h e i s s u eo ft h es p e c t r a lr a d i u so ft r i c y c l i cg r a p h s ，m a i n l yi n c l u d e s ： i ti n t r o d u c e st h ep a p e r sr e s e a r c hb a c k g r o u n da n ds i g n i f i c a n c e ，i n c l u d i n gt h e d e v e l o p m e n to far e p r e s e n t a t i v ea th o m ea n da b r o a dr e g a r d i n gt h i sa s p e c t b a s e do nt h i sr e s e a r c hb a c k g r o u n da n dp r o f o u n dd i s c u s s i o no nt h es t a t u sq u o ， i tf u l l ys h o w st h em a i nw o r k sn e c e s s i t ya n di n n o v a t i o n w es t u d yt h es p e c t r a lr a d i u so ft r i c y c l i cg r a p h so n 礼v e r t i c e sw i t hkp c n d e n t v e r t i c e s t h en - v e r t e xt r i c y c l i cg r a p hw i t hkp e n d e n tv e r t i c e sh a v i n gm a x i m u m s p e c t r a lr a d i u si sc h a r a c t e r i z e d t h es p e c t r a lr a d i u so ft r i c y c l i cg r a p h sw i t hn v e r t i c e sa n dd i a m e t e rdi ss t u d i e d - t h en - v e r t e xt r i c y c l i cg r a p hw i t ho fg i v e n d i a m e t e rdw i t hm a x i m u ms p e c t r a l r a d i u si sd e t e r m i n e d w ca l s os t u d yt h es p e c t r a lr a d i u so ft r i c y c l i cg r a p h so nn v e r t i c e sw i t hp e r f c c t m a t c h i n g s t h e2 m v e r t e xt r i c y c l i cg r a p hw i t hw i t hp e r f e c tm a t c h i n g sh a v e m a x i m u ms p e c t r a lr a d i u si sd e t e r m i n e d k e yw o r d s ：s p e c t r a lr a d i u s ；t r i c y c l i cg r a p h s ；p e n d e n tv e r t e x ；d i a m e t e r ；p e r f e c t m a t c h i n g i i 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文；是本人在导师指导下，独立进行研究t 作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：取显五日期：z 口。7 年6 月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华 中师范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 作者签名：酉火显五 日期：2 口。 年月日 导师签名：礅 日期：z 呻年占月日 本人已经认真阅读“c a m s 高校学位论文全文数据库发布章程”，同意将本人的学位 论文提交“c a m s 高校学位论文全文数据库”中全文发布，并可按“章程”中的规定 享受相关权益。同意论文提交后滞后：口半年；口年；口二年发布。 作者签名：耻显五 日期：如叼年6 月f 日 导师签名：歹玺转熟 日期：砷年石月旧 硕士学位论丈 m a s t e rst t t e s i s 第一节绪论 本节首先介绍了课题的研究背景及研究意义与国内外研究现状然后列出本文 所研究的主要内容 1 1研究背景及研究意义 图的谱半径指的是其邻接矩阵的最大特征值图的谱半径在化学上有很重要 的作用c v e t k o v i d $ 口g u t m a n d c v e t k o v i d ，i 。g u t m a n ，c r o a tc h e ma c t a1 9 7 7 ，4 9 ， 1 1 5 1 指出一个分子所对应的图的谱半径可以用来衡量分子的分支结构每一类图 可以对应不同的分子结构，故研究不同图类的谱半径是有意义的由于图的谱半径 在图谱理论中的重要作用，近几年在这一方面的研究成果很多另外，a b r u a l d i ， e s s o l h e i d ( o nt h ei n d e xo fc o n n e c t e dg r a p h s ，p u b l i n s t m a t h ( b e o g r a d ) 3 9 ( 5 3 ) ( 1 9 8 6 ) 4 5 5 4 1 提出了关于图的谱半径的下面问题：给定一类图的集合够，在这 类图中找到谱半径的上界并且刻画出谱半径上界所对应的图 1 2本课题国内外主要研究现状 图的谱半径指的是其邻接矩阵的最大特征值记做j d ( g ) 对于不同的图类，有 很多关于谱半径的结果g u oe ta 1 2 4 ，4 1 研究了具有礼个顶点且含有k 个悬挂点的 单幽图和双圈图的谱半径g u oc ta 1 2 5 1 刻画了佗个顶点直径为d 的树的最大和第 二大谱半径；g u o $ 1 s h a of 2 3 亥1 j 画了n 个顶点直径为d 的树的前i ：l + 1 谱半径；g u o f 2 7 1 刻画了扎个顶点直径为d 的单圈图的最大谱半径，而在f 2 6 1n 个顶点直径为d 的双 圈图的最大谱半径被讨论y u 和t i a n 4 9 1 研究了最大匹配为m 的双圈图的谱半径 对于具有完美匹配的n 点树，x uf 2 3 解决了谱半径最大的问题c h a n g 并h t i a n 6 】研 究了具有完美匹配的单圈图的谱半径问题c h a n g ，t i a n 和y u 7 】研究具有完美匹 配的双圈图的谱半径问题最近，还有很多关于l a p l a c i a n 谱半径和有向图的谱半径 的研究成果 1 硕士学位论文 m a s t e r st t t e s i s 1 3本文解决的主要问题 本文主要内容如下： 第一节：对本文研究背景，研究意义等的简单介绍 第二节：引言 第三节：本节讨论了n 个顶点且含k 个悬挂点的三圈图的谱半径问题在n 个 顶点且含k 个悬挂点的三圈图的四类图上分别找到谱半径最大所对应的图， 在此基础上比较这四个图的谱半径大小，进一步得到所有的n 个顶点且含七个 悬挂点的三圈图的谱半径最大所对应的图 第四节：本节讨论了r 1 个顶点且直径为d 的三圈图的谱半径问题在n 个顶点 且直径为d 的三圈图的四类图上分别找到谱半径最大所对应的图，在此基础 上比较这四个图的谱半径大小，进一步得到所有的n 个顶点且直径为d 的三圈 图的谱半径最大和第二大所对应的图 第五节：本节讨论了佗个顶点且具有完美匹配的三圈图的谱半径问题在扎个 顶点且具有完美匹配的j 圈图的四类图上分别找到谱半径最大所对应的图， 在此基础上比较这四个图的谱半径大小，进一步得到所有的n 个顶点且具有 完美匹配的三圈图的谱半径最大所对应的图 第六节：本节讨介绍了关于本论文的延伸，在此论文基础上我们还可以有做 许多很有意义的工作 参考文献，在校期间发表的主要论文及致谢 1 4本文用到的主要符号 r ：阶为佗的路； g ：阶为n 的圈； k 1 n 一1 ：阶为礼的星图； 。缵：所有礼个顶点且含k 个悬挂点的三圈图构成的集合； 磊，d ：所有礼个顶点且直径为d 的三圈图构成的集合； 少( 2 尼) ：所有具有完美匹配的2 南个顶点的三圈图的集合； 2 硕士学位论文 m a s t e r st h e s i s 第二节引言 在本论文中考虑的所有图都是有限，无定向的简单图设c = ( ve ) 是一个 含n 个顶点的图并且设a ( g ) 是其邻接矩阵因为a ( g ) 是对称的，所以它的特征 值是实的不失一般性，我们记这些特征值为入1 ( g ) 入2 ( g ) k ( g ) ，称 它们为g 的特征值d e t ( a 一a ( g ) ) 称为g 的特征多项式，记为( g ；入) 最大特征 值入1 ( g ) 称为g 的谱半径，记为p ( g ) 如果g 是连通的，贝t j a ( g ) 是不可约的，由非负 矩阵的p e r r o n - p r o b e n i u s 理论，我们知道，) ( g ) 的重数为l 且存在唯一的正的特征向 量对应于，) ( g ) 我们称这个特征向量为g 的p e 舢他向量 一个图c 7 = ( v 7 ，e 7 ) 是图g = ( ue ) 的子图如果有v ( c 7 ) v ( c ) 且e ( c 7 ) e ( g ) ，记为g ，g 如果g ，g ，则g ，称为g 的真子图，记为g ，cg 如果y ( g ，) = y ( g ) ，则g 7 称为g 的生成予图设g x 或g x y 表示在g 中去掉点z y ( g ) 或 去掉边x y e ( g ) 得到的图类似地，g + z 可表示在g 上加入边x y 譬e ( g ) ，这 里z ，y 矿( g ) 对于图g 的一个点v ，g ( u ) 是v 点在g 中的邻点集合，g ( 口) 集合的 数目称为 点的度，记为d ( u ) 令6 ( g ) = m i n n a ( v ) ：v y ( g ) ，a ( g ) = m a x n cv ) ： v y ( g ) a b r u a i d i ，e s s o l h c i d 提出了关于图的谱半径的下面问题：给定一类图的集 合够，在这类图中找到谱半径的上界并且刻画出谱半径上界所对应的图是有意义 的 设h ( 佗，亡) 是所有n 个顶点且具有n + t 条边的连通图，这里- 1 t ；死( 仡一1 ) - n n n ( - , ，一1 ) 是所有礼个顶点的树m 6 ，7 ，2 3 1 我们知道：( 1是其中谱半径最大对,n-1 应的图而r 是谱半径最小对应的图对于0 t 冬1 ，【6 7 ，2 2 2 6 】得到许多关于谱半 径的结论在本论文中，我们讨论t = 2 的情况 我们知道：3 4 1 已经完全刻画了含n 个顶点的三圈图的结构，即一个三圈图g 包 含至少3 个圈而最多7 个圈且不包含5 圈故三圈图可以分为四类，这四类三圈图的 结构如下面的图1 图4 所示 下面我们列出一些论文中需要用到的引理 引理2 1 ( a 6 ，4 3 1 ) 设( ；是一个连通图且j 口( g ) 是4 ( g ) 的特征值今“，钉是g 的 两点，c f ( 秒) 勋点的度假设u l ，u 2 ，u 。( u ) j 7 v ( u ) ( 1 s d ( u ) ) 并且设z = ( z 1 ，z 2 ，z n ) 是a ( g ) 的p e 肿佗向量，这里鼢对应点仇( 1 i 佗) 设g + 是通过去 掉g 的边u 饥而添上边“( 1 i s ) 得到的图如果z u x v ，则p ( g ) p ( c + ) 3 硕士学位论文 m a s t e r st h e s i $ o o oo ，一oc p 一 扣& 一n p 一丁一忙 旺，o 沪石f u ( g ) ( ) 一o 蠹6o o 6 一oo 一o ( f )( i i ) ( i i i )( i v )( v ) 图2 ：( i ) 是图尸( f ，p ，q ) ，( i i ) ，( i i i ) ，( i v ) ，( v ) 是恰包含4 个圈的三圈图的4 种结构 国 的3 种结构 图4 ：恰包含7 个圈的三圈图的1 种结构 引理2 2 ( 【2 6 】) 设g ，g 7 ，g 三个点不交的连通图假设u ，v # _ c e j 两点，仳7 是g 7 的点而是g 的点设g 1 是由g ，g 7 ，g 7 7 通过重合乱与札7 和t j 和得到的图设g 2 由g ， g 7 ，g 通过重合仳，仳7 ，u t t 得到的图设g 3 由g ，g 7 ，g 通过重合口，u t ，u t t 得到的图则或 者有p ( v 1 ) 2 , 且d ( v i ) = 2 ，这里o ( g l ；a ) 对所 有a p ( a 1 ) 成立i ( i i ) ( 【1 0 ，1 2 ) 如果咖( g 2 ；a ) ( g l ；a ) 对所有入j d ( g 2 ) 成立，则p ( g 1 ) p ( c 2 ) ； ( i i i ) ( 【3 1 】) 如果岛是g l 的真子图且g l 是一个连通图，则p ( g 2 ) 弘1 引理3 2 ( 【4 1 】) 若图g 和阿都恰有一个特征值大于一个常数口，如果 ( g ，j d ( ) ) 0 ，贝4 p ( g ) 0 ， 和 ( r 。一1 ；入) ( b 。；入) ( r ；l ；a ) ( 只。；入) 0 对所有i = 2 ，3 ，k 另一方面，因为虬是玩( 1 ) 的子图，由引理2 5 ，可得到p ( b 4 ( 1 ) ) p ( 虬) = 2 这 样，当入p ( b 4 ( 1 ) ) 2 ，可以得到 2 a 4 + 2 k 3 一入2 2 入一1 0 ，3 a 3 + 4 a 2 5 a 一6 0 ，a 2 一l 0 ，入5 3 a 3 + 2 a 0 故，f ( a ) + 9 ( 入) 0 ，i e ，咖( 反( 1 ) ；入) ( b 3 ( 1 ) ；a ) 对于a j d ( b 4 ( 1 ) ) 成立由引 理2 5 ，p ( b a ( 1 ) ) p ( 反( 1 ) ) 引理得证 口 b t ( 1 ) 表示在肠的一点( 记为口) 粘上七条长度几乎相等的路得到的n 阶三圈图 对b 7 ( 1 ) 的 点利用引理2 8 ，我们得到 咖( b 7 ( 1 ) ；a ) = ( 入4 6 a 2 8 a 一3 ) ( r 。；入) 矽( 毋。；a ) k 一( 入3 3 a 一2 ) 曲( 最，；a ) ( 最i 一1 ；入) ( 日。；入) i = 1 注意b 3 ( 1 ) 和b 7 ( 1 ) 存在当且仅当老l ，礼k + 7 引理3 5 假设b 3 ( 1 ) 和口7 ( 1 ) 都存在，则岛( 1 ) 的谱半径大于b 7 ( 1 ) 的谱半径 8 证明：在b 7 ( 1 ) 中粘在v a 的最长路的长度记为2 ( z 2 ) ，并假设这样的路有t 条 情况1 3 设b 3 是一个类似于b 3 ( 1 ) 的图，其中粘在v 点的路都包含z 1 个顶点设b 7 是一 个类似于b 7 ( 1 ) 的图，其中粘在v 点的路都包含z 个顶点显然，玩是b 3 ( 1 ) 的导出子 图并且b 7 ( 1 ) 是b 7 的导出了图这样，由引理2 5 ， p ( b 3 ) p ( b 3 ( 1 ) ) 等式成立当且仅当佗= ( f 一1 ) k + 7 并且， p ( b 7 ) p ( b t ( 1 ) ) 等式成立当且仅当n = i k + 4 这样为了证明引理，我们需要证明式子p ( b 7 1 p ( b 3 ) 成立下面我们证明这 个式子成立 由引理3 1 ，图b 3 和b 7 都恰有一个特征值大于3 ( 这是因为b 3 一u 和b 7 一v 的分支 都是路和虬，路的谱半径不小于2 ，而如的谱半径是2 所以a 2 ( b 3 ) o 成立当且仅当 7 i 咖( 只；7 ) 一1 【( r 4 6 r 2 8 r 一3 ) 砂( r ；7 ) 一七( 7 3 3 r 一2 ) 砂( 毋一1 ；r ) 】 0 当且仪当 当且仅当 ( r 4 6 r 2 8 r 一3 ) 矽( r ；7 ) 尼( r 3 3 r 一2 ) ( r l ；7 ) ( 7 4 6 7 2 8 r 一3 ) 妒( 毋；r ) 、( ? 7 9 r 5 6 r 4 + 1 5 r 3 + 1 2 r 2 7 r 一6 ) 砂( r 一1 ；7 ) ， 7 ( 7 6 3 r 4 + 3 r 2 一1 ) ( r 一2 ；r ) 、 当且仅当 r 3 3 r 一2 ) ( 忍一1 ；r ) ( r 1 0 9 r 8 8 r 7 + 1 8 r 6 + 2 4 r 5 1 0 r 4 2 4 r 3 3 r 2 + 8 r + 3 ) ( 最；7 ) 咖( b 一2 ；r ) ( 7 1 0 1 2 r 8 8 r 7 + 4 2 r 6 + 4 8 r 5 4 0 r 4 7 2 r 3 3 r 2 + 3 2 r + 1 2 ) ( 只一1 ；r ) 2 由引理2 7 ，我们得到 ( r ；r ) = ( 7 r 1 一碍“) ， 这里r = ( r + “：矿五) ，r 2 = ( 7 一“巧) 是方程z 2 一r x + 1 = o 的根由韦达 定理，7 l + r 2 = r ；r l r 2 = 1 ，故我们有 r ；+ 鹰= ( r l + r 2 ) 2 2 r l r 2 = r 2 2 ， r ：+ 蠢= ( 7 ；+ 咤) 2 2 r 2 l r 2 2 = ( r 2 2 ) 2 2 利用上面的表达式，( b 7 ；r ) o 局2 立当且仅当 万1 j ( r 1 0 _ 9 r 8 _ 8 r t + 1 8 7 6 + 2 4 r 5 - 1 0 r 4 - 2 4 r 3 _ 3 r 2 + 8 r + 3 ) ( r r l 一口1 ) ( r i 一古1 ) ：， r 2 4 、r 1 0 1 2 r 8 8 r 7 + 4 2 r 6 + 4 8 r 5 4 0 r 4 7 2 r 3 3 r 2 + 3 2 r + 1 2 ) ( 以r 5 ) 2 1 0 当且仅当 有 ( r + r 芋) ( 3 r 8 2 4 r 6 2 4 r 5 + 3 0 r 4 + 4 8 r 3 2 4 r 一9 ) r 1 2 1 3 r 1 0 8 r 9 + 6 0 r s + 5 6 r 7 1 3 0 r 6 1 6 8 r 5 + 9 7 r 4 + 2 0 0 r 3 + 1 5 r 2 8 0 r 一3 0 ( 3 3 ) 现在我们证明当f 2 ，。z = r + r 茅是严格递增的因为r + r 争= 1 r 4 t 广+ 1 ，我们 大于1 当且仅当 即是 显然当r l 1 不等式成立 a l + 1r 笋“+ 1 一a l2 而 r r 。+ r i r 4 ：+ 4 + 1 r 4 m + r ； ( r + 2 1 ) ( r ；一1 ) 0 前面我们已经讨论了当( 口7 ；r ) o 成立当且仅m ( 3 3 ) 式成立现在我们知道 如果2 = 2 时( 3 3 ) 式成立，那么当2 2 时( 3 3 ) 式也成立 对z = 2 ，我们有 当且仅当 ( r ；+ r 2 a ) ( 3 r 8 2 4 r 6 2 4 r 5 + 3 0 r 4 + 4 8 r 3 2 4 r 一9 ) r 1 2 1 3 r 1 0 8 r 9 + 6 0 r 8 + 5 6 r 7 1 3 0 r 6 1 6 8 r 5 + 9 7 r 4 + 2 0 0 r 3 + 1 5 r 2 8 0 r 一3 0 2 r 1 2 2 3 r 1 0 1 6 r 9 + 7 2 r 8 + 8 8 r 7 3 8 r 6 9 6 r 5 4 6 r 4 8 r 3 + 2 1 r 2 + 3 2 r + 1 2 0 令 f ( r ) = 2 r 1 2 2 3 r 1 0 1 6 r 9 + 7 2 r 8 + 8 8 r 7 3 8 r 6 9 6 r 5 4 6 r 4 8 r 3 + 2 1 r 2 + 3 2 r + 1 2 注意到当7 3 ，有2 r 1 2 ；r 1 2 + r 1 1 故 f ( r ) 矿5 1 2 + 7 1 l 一2 3 r 1 。- 1 6 r 9 + 7 2 r s + 8 8 r 7 - - 3 8 r 6 - 9 6 r 5 _ 4 6 r 4 _ 8 r 3 1 1 硕士学位论文 m a s t e r st h e s i s + 2 1 r 2 + 3 2 r + 1 2 = l 矿51 2 2 3 r 1 。+ 6 7 r 8 ) + r1 _ 1 6 r 9 + 6 4 r 7 ) + ( 5 r a - 3 8 r 6 - 4 6 r 4 ) + ( 2 4 r 7 9 6 r 5 8 r 3 ) + ( 2 1 r 2 十3 2 r + 1 2 ) 容易验证当7 3 1 0 1 9 ，有；7 1 2 2 3 r l o + 6 7 r 8 0 ，r 1 1 1 6 r 9 + 6 4 r 7 0 ，5 r 8 3 8 r 6 4 6 r 4 0 ，2 4 r 7 9 6 r 5 8 r 3 0 ，2 1 r 2 + 3 2 r + 1 2 0 即是，当r 3 1 0 1 9 时， ( r ) 0 因为r = p ( b 3 ) 3 3 9 2 3 ，所以我们证明了妒( b 7 ；j d ( b 3 ) ) 0 ，这样由引 理3 2 ，我们得到 j d ( b 3 ) p ( b 7 ) 进而 p ( b a ( 1 ) ) p ( b 7 ( 1 ) ) 情况2 1 t 2 ，k 2 在这种情况下，显然有粘在b 7 ( 1 ) 上v 点的最长路包含2 个顶点，粘在b 3 ( 1 ) 上u 点 的最短路包含z 一2 个顶点，这里z 3 这样，令蟛是一个类似于玩( 1 ) 的图，其中粘 在v 点的路都包含z 一2 个顶点显然，联是既( 1 ) 的导出子图并且b 7 ( 1 ) 是b ，的导出 子图这样，由引理2 5 ， p ( 毯) p ( b a ( 1 ) ) 等式成立当且仅当n = f f 一2 ) k + 7 并且 p ( b 7 ) p ( b 7 ( 1 ) ) 等式成立当且仅当n = i k + 4 这样为了证明引理，我们需要证明式子p ( b 7 ) p ( 弼) 成立下面我们证明这 个式子成立 由引理3 1 ，图彤和b 7 都恰有一个特征值大于3 ( 这是因为彤一 和b 7 一钉的分支 都是路和虬，路的谱半径不小于2 ，而虬的谱半径是2 所以a 2 ( 耳) o 成立当且仅当 2 r 1 3 2 6 r 1 1 1 6 7 1 0 - i - 1 0 8 r 9 + 1 1 2 r 8 1 6 4 r 7 2 4 0 r 6 + 7 4 r 5 + 2 0 8 r 4 + 3 0 r 3 6 4 r 2 2 4 r 0 令 2 r 1 2 2 6 r 1 0 1 6 r 9 - i - 1 0 8 r 8 + 1 1 2 r 7 1 6 4 r 6 2 4 0 r 5 + 7 4 r 4 + 2 0 8 r 3 + 3 0 r 2 6 4 r 一2 4 ( 2 r 1 2 2 6 r 1 0 1 6 r 9 + 9 2 r 8 + 8 8 r 7 ) + ( 1 6 r 8 1 6 4 r 6 - i - 7 4 r 4 ) + ( 2 4 r 7 2 4 0 r 5 + 1 4 4 r 3 ) + ( 6 4 r 3 6 4 r ) + ( 3 0 r 2 2 4 ) 容易验证当r 3 1 2 6 ，1 6 r 8 - 1 6 4 r 6 + 7 4 r 4 0 ，2 4 r 7 - 2 4 0 r 5 + 1 4 4 r 3 0 ，6 4 r 3 - 6 4 r 0 3 0 r 2 2 4 0 令 夕( r ) = 2 r 1 2 2 6 r 1 0 1 6 r 9 - t - 9 2 r 8 - i - 8 8 r 7 当r 3 ，夕7 ( r ) = 2 4 r 1 1 2 6 0 r 9 1 4 4 r 8 + 7 3 6 r 7 - i - 6 1 6 r 6 0 ，这表明当r 3 ，夕( r ) 是 严格递增的由于夕( 3 ) 0 ，所以当r 3 时，g ( r ) 0 即是当r 3 1 0 1 9 ，y ( r ) 0 又因为7 l = p ( 耳) 3 2 6 3 5 ；故可以得到( b 7 ；j 9 ( 毯) ) 0 ，利用引理3 2 ， 所以 p ( 聪) p ( b 7 ) p ( b 3 ( 1 ) ) ，( b 7 ( 1 ) ) 情形3 t = 1 ，尼= 1 在这种情形下 ( 恳( 1 ) ；a ) = ( a 7 9 a 5 6 , k 4 - t - 1 5 a 3 + 1 2 a 2 7 a 一6 ) ( 只一3 ；入) 一( 久6 3 入4 + 3 a 2 1 ) ( 冠一4 ；入) ， ( b 7 ( 1 ) ；a ) = ( 入4 6 入2 8 入一3 ) 咖( 局；入) 一( a 3 3 a 一2 ) 咖( r 一1 ；a ) 由引理3 1 ，图鼠( 1 ) 和b 7 ( 1 ) 都恰有一个特征值大于3 ( 这是因为b 3 ( 1 ) 一v 和 b 7 ( 1 ) 一u 的分支都是路和配，路的谱半径不小于2 ，而的谱半径是2 所以 入2 ( b 3 ( 1 ) ) o 成立当且仅当 ， 注意到 所以我们有 ( r 4 6 7 - 2 8 r 一3 ) ( r ；r ) 一( r 3 3 r 一2 ) 矽( 只一l ；r ) 0 咖( r ；r ) = ( r 3 2 r ) 咖( r 3 ；r ) 一( r 2 1 ) ( r 一4 ；r ) ， ( r l ；7 ) = ( 7 2 一1 ) 咖( r 一3 ；r ) 一r ( p l 一4 ；7 ) ， 矽( 疗7 ( 1 ) ；r ) = ( r 7 9 r 5 8 r 4 + 1 3 r 3 + 1 8 r 2 - f 3 r 一2 ) 咖( 忍一3 ；r ) 一( r 6 8 一一8 r 3 + 6 r 2 + 1 0 r + 3 ) 矽( 只一4 ；r ) 也就是说，( b 7 ( 1 ) ；7 ) o 成立当且仅当 ( r 7 9 r 5 8 r 4 + 1 3 r 3 + 1 8 r 2 + 3 r 一2 ) ( r 6 3 r 4 + 3 r 2 1 ) ( r 7 9 7 5 6 7 4 + 1 5 r 3 + 1 2 r 2 7 r 一6 ) ( 7 6 8 r 4 8 r 3 + 6 r 2 + 1 0 r + 3 ) 14 当且仅当 5 r n + 6 r 1 0 5 0 r 9 一l o o r 8 + 6 6 r 7 + 2 6 8 r 6 + 7 6 r 5 2 4 0 r 4 1 7 5 r 3 + 4 6 r 2 + 7 8 r + 2 0 0 令 y ( r 1 = 5 r 1 1 + 6 r 1 0 5 0 r 9 - 1 0 0 r 8 + 6 6 r 7 + 2 6 8 r 6 + 7 6 r 5 - 2 4 0 r 4 - 1 7 5 r 3 + 4 6 r 2 + 7 8 r + 2 0 类似情形1 和2 的证明，同样我们可以得到当r = 0 ( 7 3 ( 1 ) ) ，y ( r ) 0 利用引理3 2 ， 我们可以证明p ( b 3 ( 1 ) ) p ( b 7 ( 1 ) ) 综合情形1 3 ，结论成立 图6 ：图g ； 口 日6 ( 1 ) 表示在g ：( 图6 ) 的可点粘卜七条长度几乎相等的路得到的n 阶三圈图 风( 2 ) 表示在g ：( 图6 ) 的z 点粘上七条长度几乎相等的路得到的扎阶三圈图 使用证明引理3 5 的方法：我们可以得到下面的引理，这里不再写出完整的证明 过程注意到b 3 ( 1 ) 和b 6 ( 1 ) 都存在当且仅当七1 ：n 奄+ 7 引理3 6 假设岛( 1 ) 和隗( 1 ) 都存在，则b 3 ( 1 ) 的谱半径大于风( 1 ) 的谱半径 3 2主要定理的证明 定理3 7 设g 黠r ，k 1 则j 9 ( g ) j d ( 晚( 1 ) ) ，等号成立 - 3 且仅当g 笺 玩( 1 ) 证明：g 中的三个圈，记为q ，q ，瓯，则这三个圈的结构有7 种情况，如图1 所 示 选择g c 乡= n k , 3 使得g 的谱半径尽可能大g 中所有点记为 l ，晚，) ， g 的p e r r o n i f i 量记为z = ( z 1 ，z 2 ，z 。) ，这里兢对应点忱( 1 i 佗) 我们首先 证明下面的事实 事实1 在g 中三个圈的结构如图1 中( c ) 所示 1 5 事实l 的证明假设在g 中三个圈的结构如图1 中( 6 ) 所示令圈q 和由路 v z v 2 铆相连，这里z l _ n _ v l 在q 上，而叻在q 上不失一般性，我们假设z l 魏 再令切+ 1 是耽在圈q 上的邻点设 c + = g 一 v l v l + 1 + v l v l + l 则g + 黠，v 由引理2 1 ，我们得n p ( a + ) j d ( g ) ，与前面矛盾故2 = 1 使用相同 的方法，我q , - - i p a 得到g 中三圈的结构不可能如图l 中( d ) ，( e ) ，( ，) 或( g ) 所示这 样g 中三个圈的结构只可能是( 口) 或( c ) 利用引n 2 2 ，我们可以得到g 中三圈的结 构不可能是图l 中( n ) 所示故事实1 成立 进一步利用事实1 和引理2 2 ，可以得到g 中只可能有一棵悬挂树丁粘在三个圈 的公共点v 上 事实2 t 中每个点u 的度d ( 札) 2 事实2 的证明否则，如果存在t o e 某个点v i 的度d ( v i ) 2 令( 耽) = z l ，施，z t ， n ( v ) = w l ，w 2 ， 假设z 1 ，w 3 在连接v 和忱的路上，并r w l 和2 都在g 的某 个圈上 如果z 口z i ，令 如果z 。 p ( g ) ，p ( q ) p ( g ) ，得到矛盾故 在g 中有七条路粘在 点 事实3 粘在v 点的k 条路的长度几乎相等 事实3 的证明我们设这七条路为b 。，b 。，b 。，现在我i f e 明阪一如i 1 对所 有1 z ，j 七反证，假设存在路r 和r 。使得f l 一2 2 2 令毋。= v u l 仳2 讹。， 吃= v w l w 2 叫融设 = g 一 乱l l - 1 7 2 1 1 ) + w 1 2 7 2 1 1 ) 则口黠，一由引理2 4 ，可以得n p ( c + ) p ( g ) ，矛盾，故结论成立 事实4 - - + n q ，q 和倪的长度都是3 1 6 硕士学位论文 m a s t e r st h e s i s 事实4 的证明假设p 4 令q = v v l v 2 唧一i v ，p m = v 7 , l u 2 u m 是g 的一条悬 挂路，这里m 1 显然，g ( 名，g ，v u l u 2 u r n 不是一个内部路 令 g + = g 一 v u 1 ，v 1 ) 2 。卜卜 u 忱，? a m u 1 。 则。多，v 由引理2 3 ，我们得到p ( 口) p ( g ) ，矛盾蜘= 3 类似的，我们可 以证明q = 3 且h = 3 综合上面的事实l 一4 ，我们可以得到g = b 3 ( 1 ) 定理得证 口 定理3 8 设g 。黠，k 1 则p ( g ) p ( b 4 ( 1 ) ) ，等式成立当且仅当g 型 b a ( 1 ) 证明：设乃+ 1 ，昂+ l ，名+ 1 是三条点不交路，这晕z ，p ，q l 并且最多只有一个 是1 分别把这三条路的首尾顶点重合得到的图记为p ( z ，p ，g ) ，如图2 所示，是一 个口一图进一步，设瓯是一个圈用路p 5 把瓯和p ( t ，p ，q ) 连接起来，得到的图记为g ， 这里s 1 则g 7 有四种形式，如果图2 中( i i ) ，( i i i ) ，( i v ) ，( v ) 所示 所以，钟，4 f f l 的图可以看成是在g 7 上粘悬挂树得到的 选择g 躜，4 使得g 的谱半径尽可能大g 中所有点记为f u l ，v 2 ，) ， g 的p e r r o n l 矗j 量记为z = ( z l jx 2 ，z n ) ，这里兢对应点v i ( 1 i 佗) 使用与定理3 7 相同的方法，我们可以证明在g 7 的u 点粘上k 条长度几乎相等的 路得到g 这里g 7 是类型( i i ) 或( i i i ) 并r 目圈瓯的长度是3 令p m = v ? a l u 2 u r n 表示 粘在v 点的k 条路巾的一条，这里m 1 利用引理2 1 ，我们可以证明g 7 只可能是类型0 i i ) 为了方便，假设a 是p ( 1 ，