（数学专业论文）直径为n4的谱半径第二小的图.pdf

略 0 i l t h e g r a p h so fd i a m e t e rn - 4w i t ht h es e c o n d s m a l l e s ts p e c t r a lr a d i u s at h e s i ss u b m i t t e df o rt h ed e g r e eo fm a s t e r c a n d i d a t e ：j i a n gj i n g j i n g s u p e r v i s o r ：p r o f t a ns h a n g w a n g c o l l e g eo f m a t h e m a t i c sa n dc o m p u t a t i o n a ls c i e n c e s c h i n a u n i v e r s i t yo fp e t r o l e u m ( e a s tc h i n a ) 85川66mmm7，8iii1洲y 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其它人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中做出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：墨静趋 日期：仞f f 年多月弓日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机 构) 送交学位论文，以学术交流为目的赠送和交换学位论文允许学位论文被查阅、 借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、 缩印或其它复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：兰鱼篮 指导教师签名： 日期：l 年加弓日 日期：扣f 年月3 日 摘要 图谱理论是代数图论的一个重要研究课题，它包括图的邻接谱和拉普拉斯谱等。树 是一种十分特殊而重要的图，正是因为树的性质的特殊性，所以很多连通图的研究往往 要借助于树的特性来进行。 这篇论文将研究图的邻接谱。目前利用图的最大谱半径对图进行定序已经有了许多 较好的结论，但是利用图的最小谱半径进行定序得到的结论相对较少。本文在已有结论 的基础上将进一步确定顶点数为n 且直径d ，l 一2 ，n 一3 ，z 一4 的所有连通图中谱半径第 - - + 的连通图。本文主要内容分为三部分： 1 第一章主要是对图谱理论进行了总的概述，介绍了图谱的相关概念和记号，并对 全文进行了结构性的说明。 2 第二章首先对比较简单的直径为刀一2 的树进行定序；然后对直径为刀一3 和以一4 的树进行分类，研究每类树的性质、按照最小谱半径对树进行定序并且找出每类树中谱 半径第- - + 的树。 3 第三章主要是证明直径为n 一2 、刀一3 、n 一4 的刀阶连通图中，谱半径第二小的 图必为树。 关键词：图，树，最小谱半径，定序，直径 t h eg r a p h so fd i a m e t e rn 4w i t ht h es e c o n d s m a l l e s ts p e c t r a lr a d i u s j i a n gj i n g ji n g ( m a t h e m a t i c s ) d i r e c t e db yp r o f t a ns h a n g w a n g a b s t r a c t t h es p e c t r a lo fg r a p h si sa l li m p o r t a n tr e s e a r c hs u b j e c ti na l g e b r a i cg r a p ht h e o r y , w h i c h i n c l u d e st h ea d j a c e n c ys p e c t r u ma n dl a p l a c i a ns p e c t r u mo fg r a p h s ，a n ds oo n t h et r e ei sa v e r ys p e c i a la n di m p o r t a n tg r a p h b a s e dt ot h i sr e a s o n ，m a n ys t u d yf o rc o n n e c t e dg r a p h so f t e n r e l yo n t r e e s t h ep a p e rw i l ls t u d yt h ea d j a c e n c ys p e c t r u mo f 伊印l l s a tp r e s e n tt h e r eh a v eb e e nm a n y g o o dc o n c l u s i o n so r d e r i n gg r a p h sb yt h em a x i m u ma d j a c e n c ys p e c t r u mr a d i u so fg r a p h s ，b u t t h e r eh a v eb e e nl i t t l ec o n c l u s i o n so r d e r i n gg r a p h sb yt h em i n i m u ma d j a c e n c ys p e c t r u mr a d i u s o fg r a p h s o nt h eb a s i so ft h ep r e v i o u sc o n c l u s i o n s ，t h ep u r p o s eo ft h i sp a p e ri st of r t h e r d e t e r m i n et h ec o n n e c t e dg r a p h 、析t ht h es e c o n ds m a l l e s ts p e c t r a lr a d i u si nt h es e to fa l lg r a p h s w i t ho r d e rna n dd i a m e t e r d n - - 2 ，刀一3 ，疗一4 t h ep a p e rw i l lb ea r r a n g e da sf o l l o w i n g ： 1 t h ef i r s tc h a p t e rw i l li n t r o d u c et h eg e n e r a lo u t l i n eo ft h eg r a p hs p e c t r u mt h e o r y , r e l a t e dc o n c e p t sa n dn o t a t i o n s ，a n de x p l a i nt h es t r u c t u r eo ft h i sp a p e r 2 t h es e c o n dc h a p t e rw i l lf i r s to r d e rt r e e si nt h es e to ft r e e sw i t ho r d e r ，la n d d i a m e t e rn 一2 ，t h e np a r t i t i o nt h et r e e s 、杭t hd i a m e t e rn 一3a n d 珂一4i n t os o m et y p e s ， i n v e s t i g a t et h e i rp r o p e r t i e s ，o r d e rt h e mi ne a c ht y p ea c c o r d i n gt o t h em i n i m u m s p e c t r a lr a d i u s ，a n dd e t e r m i n et h et r e e s 埘t 1 1t h es e c o n ds m a l l e s ts p e c t r a lr a d i u si n e a c ht y p e 3 t h et 1 1 i r dc h a p t e rw i l lp r o v et h a tt h eg r a p hw i t l lt h es e c o n ds m a l l e s ts p e c t r a lr a d i u s m u s tb et r e e si nt h es e to f g r a p h s 、i t h 聆v e r t i c e sa n dd i a m e t e r n 一2 ，行一3 ，疗一4 k e y w o r d s ：g r a p h s ，t r e e s ，m i n i m u ms p e c t r a lr a d i u s ，o r d e r i n g ，d i a m e t e r 目录 第一章绪论l 1 1 概述1 1 2 基本的概念和记号2 1 3 本文的工作安排3 第二章给定直径刀一2 ，n 一3 ，n 一4 的谱半径第二小的树5 2 1 直径为玎一2 的谱半径第二小的树5 2 1 1 相关引理5 2 1 2 结论。7 2 2 直径胛一3 为的谱半径第二小的树7 2 2 1 直径为刀一3 的树集合的分类一7 2 2 2 两类树集合中谱半径第二小的树8 2 3 直径为以一4 的谱半径第二小的树1 0 2 3 1 直径为刀一4 的树集合的分类。1o 2 3 2 三类树集合中谱半径第二小的树16 第三章给定直径刀一2 ，n 一3 ，刀一4 的谱半径第二小的连通图2 1 3 1 直径为n 一2 的谱半径第二小的连通图2 l 3 2 直径为n 一3 的谱半径第二小的连通图2 3 3 3 直径为刀一4 的谱半径第- d , 的连通图2 4 结论31 参考文献3 2 攻读硕士学位期间取得的学术成果3 4 致谢3 5 1 1 概述 图论起源于1 7 3 6 年哥尼斯堡七桥问题的提出，这个问题的抽象和论证方法开创了 图论的研究。1 9 3 6 年，匈牙利数学家柯尼希出版了有限图与无限图理论，这也是图 论的第一部专著。图谱理论的核心是图的各种谱，研究对象包括邻接谱、拉普拉斯谱、 无号拉普拉斯谱等。1 9 5 7 年，l c o l l a t z 和u s i n o g o w i t z 在一篇文章中已经提到：如果g 是甩阶连通图，则 2 c o s 二= _ p ( g ) 门一1 ， 十l 其中左边等号成立当且仅当g 兰只，右边等号成立当且仅当g 兰k 。但是真正最早 明确提出研究图的邻接谱的学者是s a c h sh 和h o f f m a naj ( 1 9 6 9 年) 。到了1 9 7 1 年， c v e t k o v i 6dm 在他的博士论文中引用了8 3 篇1 9 7 0 年以前的文献，这些被归纳的文献都涉 及到图的邻接特征值【l 】。关于图的邻接谱理论的最新进展，在1 9 9 5 年出版的专著s p e c t r a o f g r a p h s 的第三版的附录都有详尽的叙述。最近几十年中，网络流问题的问世和计算 机科学的发展，对图论的研究起着极大的推动作用，图论也为其提供了合理的数学模型 和求解方法。 图谱研究的主要途径是通过图的各种矩阵来建立图的拓扑结构和图的矩阵表示的 置换相似不变量之间的联系。图谱包含了许多与网络的物理性质有关的结论，例如鲁棒 性和直径，以便建立图与邻接矩阵的特征值的密切联系，详见文献【2 ，3 】。文献 4 己证 明图的谱半径在网络病毒传播中起着非常重要作用，并提出了s i s 感染模型。s i s 模型假 设网络中的节点是下面两种状态的一种：被感染和具有传染性，健康和容易受到感染。 s i s 模型假设了瞬时状态转换，即一旦一个节点被感染，它是具有传染性的，同样地， 一个节点治愈后它是容易被再次感染的。 在文献 5 】中，作者详细描述了图的直径和谱半径与图的网络结构的病毒传播之间的 关系。流行病学理论( 详见文献 6 】) 提出了该模型中易感染的阈值f 。传染阈值在文献 4 】中定义为：f = 1 p ( a ) 。因此，可以发现谱半径越小，网络结构的反病毒传染的稳定 性就越强。这引出了一个问题：如何寻找刀个顶点的连通图中具有较小谱半径的图? 已经知道路只在所有图中具有最大的传染阈值的，但它的直径d = 刀一l 也是最大 的。一般来说，通信网络的设计要求网络结构的直径较小，因为穿过链接的分节点越多， 第一章绪论 网络运行的服务质量就越差。出于这个原因，同时也要考虑到了图的直径的影响，问题 转化为：如何找出给定直径的行个顶点的连通图中有较小谱半径的图? 这也是研究较小 谱半径的意义之一。 就此问题，v a nd a mer 和k o o i jre 等人在文献【5 】中确定了直径是 。 ，2 ，l 兰j ，”一3 ，刀一2 ，以一) 的谱半径最小的连通图，并且提出了一个猜想；袁西英等人证明了v a nd a me r 和k o o i j r e 的猜想在e ：4 时是成立的7 1 ；c i o a bs m 等人证明上述猜想在e ：5 时是成立的， 并且指出该猜想在e 6 时不成立【8 】；f r a n c e s c ob e l a r d o 等人确定了直径d 4 的所有树 中谱半径最小的树9 1 。本文将进一步确定顶点数为刀且直径d n 一2 ，疗一3 ，甩一4 的所有 连通图中谱半径第二小的连通图。 1 2 基本的概念和记号 本文中指出的图均为无向简单连通图，下面是本文所涉及的基本概念和记号。 设g 是一个顶点集为v ( g ) 且边集为e ( g ) 的简单连通图，其中 y ( g ) = h ，吃，屹) ，e ( g ) - - e , ，e 2 ， g 的邻接矩阵彳( g ) = ( 口，) 是一个甩门的( 0 ，1 ) 矩阵，其中当v 和邻接时，= 1 ；当_ 和v ，不邻接时，= 0 。 将g 的特征多项式定义为d e t ( 2 i 一彳( g ) ) ，简记为o ( g ，x ) 或o ( x ) ，它所对应的根称 为图g 的特征值。因为彳( g ) 是实对称矩阵，所以它的特征值均为实数。不妨假设它的 特征值按照下降的次序排列为 2 1 ( g ) 五( g ) 丸一l ( g ) 以( g ) ， 其中，五( g ) 称为图g 的谱半径，记为p ( g ) 。令g ( v ) 表示图g 中任一个顶点v 的所有 邻接点的集合( 简记为( 1 ，) ) 。对任意v v ，g 中与顶点v 相关联的边的条数称为该顶 点的度，这里用比( 1 ，) 表示g 中点1 ，的度( 或简记为a ( v ) ) ，a ( g ) 表示图g 的顶点最大 度。度为l 的顶点叫做悬挂点；与悬挂点相关联的边叫做该点的悬挂边。 图g 中顶点和边的交替序列记为v o e _ l v ) e 2 一1 ，对1 f m ，边q 的两个端点 是一一。和巧，则称该序列为g 的一条路径。边和点互不相同的路径叫做路。 路中边的条数称为该路的长度。起点和终点相同的路称为圈。在这里，具有，z 个顶 2 中国石油人学( 华东) 硕上学位论文 点的路通常用只表示，具有r 1 个顶点的圈用g 来表示。 在连通图中，把顶点u 和v 之间的所有路中长度最小的长度称为顶点u 和v 之间的距 离，记为d ( u ，) 。 图g 的直径，记为d = d ( g ) ，是g 中任意两顶点间距离的最大值，即 d ( g ) = m a x d ( u ，v ) ：甜，v ，u ，) 。 设川屹略是图g 的一个路，如果它满足 d ( ，) 3 ，d ( 啊) = d ( v 2 ) = = d ( v k 1 ) = 2 ，d ( v k ) = 1 ， 则称它是图g 在1 ，点引出的长度为k 的悬挂路。 设圳是连通图g 的一条边，瓯是删除边u v ，然后增加一个新的点w 与两个新的边 删和w 得到的图。从g 到瓯的过程我们称之为g 对边u v 的一次剖分。 没有圈的连通图称为树，常用丁表示。 设丑= v ，v 2 唯是一条路，篇；j ：z 冀表示在路只的顶点、( 待1 , 2 ，f ) 上引出一条 长度为n j 的悬挂路得到的树，其中 铂2 ，啊j | 一1 ，啊sm 2 鸭。 显然，篇；3 埘。- ；1 t t 的顶点数为惕+ + 吩+ 珥+ 后。 1 3 本文的工作安排 c v e t k o v i 6dm 曾经指出了图谱理论的几个迸一步研究方向，其中之一就是对图进 行分类和定序( c l a s s i f y i n ga n do r d e r i n gg r a p h s ) 1 1 。利用图的谱半径对图进行定序一直 是图谱研究的热点问题之一，在文献 5 】中，v a nd a mer 和k o o i jre 已经确定了直径 。 ，2 ，l 三j ，”一3 ，n 一2 ，”一) 的谱半径最小的连通图，并且他们提出了下面的一个猜想。 勰对固执和足够姗，傣丁；n 引- e + 。脚个顶点和直陋的所有 连通图中谱半径最小的唯一图。 关于该猜想已经取得如下结论： ( 1 ) 袁西英等人证明该猜想对e = 4 成立7 1 。 ( 2 ) c i o a bsm 人证明该猜想对e = 5 也成立，且指出该猜想对e 6 不成立【8 1 ； 3 第一章绪论 ( 3 ) f r a n c e s c ob e l a r d o 等人确定了直径d 4 的所有树中谱半径最小的树1 9 1 。 本文将在文献 7 】的基础上确定顶点数为j r 且直径d = 1 - - 4 的所有连通图中谱半径 第- d , 的连通图。 本文后面的结构安排如下： 1 第二章首先对比较简单的直径为n 一2 的树进行定序；然后对直径为n 一3 和, 一4 的树进行分类，研究每类树的性质、按照最小谱半径对树进行定序并且确定每类树中谱 半径第- d , 的树。 2 第三章主要是证明直径为聆一2 、刀一3 、刀一4 的n 阶图中，谱半径第- - 4 , 的图必 为树。 4 中国石油大学( 华东) 硕七学位论文 第二章给定直径n 一2 ，刀一3 ，n 一4 的谱半径第- - , 1 , 6 , j 树 众所周知，在所有图中，树是一类简单的、但很重要的图，这不仅在于它的许多结 论在许多不同领域中有着广泛的应用，如计算机科学、生物科学、晶体结构学、社会科 学等等；而且在图论中，许多问题对于一般图是很难解决或者没有办法解决的，而对于 树，解决起来相对容易或是能解决的，且方法较为简单。因此，树的谱的研究对于研究 一般图的谱是非常重要的。 研究给定边独立数的树的谱半径上界的部分文献有：文献 1 1 ，1 2 给出了边无关数 为g 的聆阶树的谱半径的最大值的明确表达式，并确定了相对的树；文献 1 3 ，1 4 】给出 了边无关数为g 的，z 阶树的谱半径的第二和第三大值，并完全确定了相对的。 研究给定直径的树的拉普拉斯谱半径的部分文献有：文献【1 5 】研究给定直径和权值 的赋权树的谱半径；文献 1 6 ，1 7 研究给定直径的树的拉普拉斯谱半径。 研究树的谱半径上晃的部分文献有：文献【1 0 】得n - ；树的谱半径的最大值及第二、 第三、第四和第五大值的明确表达式，并确定了相应的树；文献 1 8 ，1 9 研究树的第二 大特征值。 研究包含圈的图的谱半径的部分文献有：文献 2 0 】给出了谱半径前六位的单圈图； 文献 2 1 研究具有完美匹配的单圈图的谱半径；文献 2 2 1 研究的是给定直径的单圈图的 谱半径；文献【2 3 】研究的是双圈图按谱半径排序问题。 以上文献大多研究是图的谱半径的上界，但确定具有最小谱半径或较小谱半径的图 相对困难一些，目前已有部分学者进行了研究，本文已经在1 1 节中做了介绍。 在这一章节中，我们的目的是确定顶点数为n 且直径d 刀一2 ，刀一3 ，甩一4 的谱半径 第- d , 的树。令r ( n ，d ) 是直径为d 并且顶点数为n 的所有连通图的集合，r ( n ，d ) 是直 径为d 并且顶点数为n 的所有树的树集合。 2 1 直径为甩一2 的谱半径第二小的树 2 1 1 相关引理 在这一节里，我们将给出一部分结论，为后面章节的证明做准备，具体如下： 引理2 1 【2 4 1 令u 是图g 的一个顶点，c ( u ) 是包含甜的所有圈的集合，则 ( g ，x ) = x ( g - u ，x ) - , ：p ( g - u - v ，x ) - 2 ( g y ( z ) ，x ) 。 v e t ( u )z e c ( u ) 引理2 2 【2 4 1 设u p 是图g 的一条割边，则 5 第二章给定直径甩一2 ，7 l 一3 ，n 一4 的谱半径第二小的树 ( “，工_ ) = ( g u v ，x ) 一( g u 一1 ，曲。 令p = v o v l l 是g 的一个路，如果顶点v o ，_ ，v k + l ( 除可能1 l d = k + l 外) 两两 互不相同，并r d ( v o ) - 3 ，d ( k ) = d ( 吃) = = d ( 咋) = 2 ，d ( 唯+ 1 ) - 3 ，则称尸是g 的一 个内路。 引理2 3 2 4 1 设g 7 是连通图g 的真子图，贝j j p ( g 7 ) p ( g ) ；如果w 是g 的内路上的边并且g g ，片篇 ，np ( g ，) p ( g ) 。 引理2 5 令t ( n ，后) 是图1 所示的玎个顶点的树。如果，l ，七一，2 ，且行1 0 ， 则p ( t ( n ，+ 1 ，k - 1 ) ) p ( g ( k + l ，一1 ) ) 。 l v l v2 1 ，3 v 开一3 一21 ，糟一l 1 ，l v 2 屹 1 ，疗一3v 卜2 屹一l 研= 置三一。 o v l1 ，2 。l 研= 置二一， h v 一4 3 一2 彤= l l = p l t 川+ ! 图2 - 2r ( n ，行一2 ) 中的三个特殊的树 f i g 2 - 2t h et h r e es p e c i a lt r e e si n1 1 ( 刀，疗一2 ) 6 中国石油人学( 华东) 硕士学位论文 2 1 2 结论 v a nd a me r 和k o o i jre 5 1 已经指出：毛ef ( n ，l 一2 ) 中谱半径最小的树是研( 见图 2 2 ) 。因为f ( n ，刀一2 ) 中每个树一定含有长度为疗一1 的路，所以每个树一定存在一个长 度为1 的悬挂路。因此，集合r ( n ，甩一2 ) 中的树可表示为霹= 叶p i i 川+ 1 ( 见图2 2 ) 。当以7 时，由引理2 6 可知，r ( n ，n 一2 ) 中树的谱半径将满足下列次序： i 型l p ( 置| ：卜。) p ( 鼻一。) p ( 鼻鲁。) p ( 鬈) p ( 露) 。 这与丁的假设矛盾。因此，a ( t ) = 3 。既然d ( t ) = n - 3 ，于是传( 丁) 2 。证毕 既然在t e ( n ，n - 3 ) 中，传( 丁) 2 。于是下面将r ( n ，刀一3 ) 划分为： 第一类：r l ( n ，n - 3 ) = t ：t r ( n ，刀一3 ) ，a ( t ) = 3 r n 3 ( 丁) = 1 ) 。 第二类：r 2 ( 刀， - 3 ) = t ：r r ( n ，刀一3 ) ，a ( t ) = 3 _ e i n 3 ( t ) = 2 。 容易发现 f l ( n , n - 3 ，= p 2 ：i = 3 , 4 , - - - , l 孚j ， r 2 ( n , r l - - 3 ) = k ：i 厶一：2 f ，z 一3 。 显然，l ，；r l ( 刀，n - 3 ) ，鬈，? f 2 ( ，z ，n - 3 ) 。 2 2 2 两类树集合中谱半径第二小的树 由文献【5 】可知f 是r l ( n ，n - 3 ) 的树中谱半径最小的图；f 是f 2 ( n ，”- 3 ) 的树中谱半 径最小的图。 在r l ( ”，2 - 3 ) 中，每个树包含长度为玎- 3 的路m v 2 一，屹一2 ，( 丁) = 3 并rn 3 ( t ) = l 。 由引理2 6 可以得出： 定理2 1 集合l ( 刀，r - 3 ) 中树的谱半径满足： p ( 磋柚) 夕( 磋柚) 从夏柚) p ( i d 。 i , - f n 存在正整数2 f p ( 露) 。 情形2 设江3 。因为t 芒 f ，片) ，特别地，t 正巧，所以有n - 3 。记丁中删除 非空点集 v ，+ 2 ，v ，+ 3 ，咋一：) 得到的图为7 1 7 ，接着记对图t 7 内路上的边连续剖分n 一一3 次得到的图为e ，由引理2 3 、引理2 4 得：p ( t ) p ( t 7 ) p ( 片) 。 情形3 设f 4 。因为t 萑 鬈，露) ，特别地，t 正巧，所以有刀一3 。记丁中删除 非空点集“，吃，v 3 ，m - 3 ，v ，+ 2 ，v ，+ 3 ，屹一2 ) 得到的图为t 7 ，接着记对图t 7 内路上的边连续 剖分n + i 一一6 次得到的图为口，由引理2 3 、引理2 4 得：p ( t ) p ( t 7 ) p ( i d 。 综合上面三种情形，得到结论p ( 丁) p ( 嚣) 。证毕 已知鬈是r 2 ( 行，n - 3 ) 的树中谱半径最小的图。由上面的定理知鬈是r 2 ( 以，以- 3 ) 中谱 半径第- d , 的树。 定理2 - 3 当刀9 时，r ( n ，刀一3 ) 中谱半径第- - d , 的是树片。 证明在r ( n ，刀一3 ) 中，当珂9 时，由引理2 2 分别得到，露的特征多项式如下： ( ) = x 9 8 x 7 + 2 0 x 5 1 8 x 3 + 4 x ， ( 露) = x 9 8 x 7 + 1 9 x 5 1 3 x 3 + 2 x 。 9 第二章给定直径n 一2 ，n 一3 ，甩一4 的谱半径第二小的树 计算得： p ( ) 2 0 5 2 8 8 ，p ( 日) 2 0 3 5 6 5 ，故p ( ) 以片) 。( 2 - 4 ) 可以知道罡不存在内路，于是由引理2 4 知p ( e ) p ( ，；) ；对e 的内路的边进行 剖分刀一9 次得到图片，由引理2 4 知p ( 日) 从露) 。故有 p ( e ) p ( e ) p ( 曰) p ( 日) 。 ( 2 5 ) 综上所述，e 露，即日是l - ( n ，n - 3 ) 中谱半径第- i j , 的树。证毕 2 3 直径为刀一4 的谱半径第- - , j , 的树 2 3 1 直径为刀一4 的树集合的分类 在这- d , 节中，主要是研究直径为玎一4 的谱半径第二小的树。文献【7 】已经证明： 在r ( n ，刀一4 ) 中，# n ：稍- 5 是具有最小谱半径的图。令吖( 江1 ，2 ，8 ) 是图2 - 4 所示的树， q ( 刀，n - 4 ) 是r ( 玩n _ 4 ) _ f 、p 2 , , - 5 中谱半径最小的树集合。首先给出r ( n ，n - 4 ) 中几个特 殊的树，如图2 _ 4 所示： j 7 “3 u 2 m 1 ，2b 一5一4 吃一3m 1 2 v 3 一6一5屹一4一3 研= 毋2 ，钟= 气p 2 ：, n ；柑- 6 v lv 2 h 2 j 盟k 4 霹= 只，j ；。2 一i m ，2b - 6 一5一4心一3 钟= 暑筹， v l屹吃- - 6 屹5一4 屹一3 g = 只墨葛 1 0 上 ，lv 2吃 j点 ( 噼，x ) = 加( ) 【( 只一，) 一( 一，) 卜x 2 ( b ) 【( 一，) 一( 只一，) 】 ( g ；5 ，功= x 3 【( 昱，一，) 一2 ( 罡。一，) + ( ，) 卜x 2 【( e 一2 ) ( 一：) - 2 0 ( e 一2 ) ( 只一4 ) + a , g 一。) ( 只一。) 】 ( 碍s + lx ) = x 3 【m ( ，2 ) - 2 g ，一4 ) + ( 足，一6 ) 】一x 2 【( 只一1 ) ( 只一2 ) 一( 只一。) ( 只一。) 一( 只一2 ) ( 只一3 ) + ( 只一3 ) ( e 一。) 】 ( g ；，x ) = 施( 最) 【( 只一，) + ( b ) ( 只- 1 0 ) 】 一( 忍) i x 2 ( 只一6 ) + ( ) ( 只一，) ， o ( g ；5 ，x ) = x 3 【( 最，一3 ) 一2 ( 芝，一5 ) + ( 最，一，) 】 一x 2 【( ( 只一，) 一( 只一，) ) ( ( 只一。) 一( 只一，) ) 】， o 、r , ，2 s + i ，x ) = x 3 【( b ，2 ) - 2 0 ( p 2 ，一4 ) + ( 最“) 】 一x 2 【( ( 只一3 ) 一( 只一，) ) ( ( 只) 一( 只一：) ) 】， ( g ；讣1 ，x ) = x 3 ( 罡，_ 2 ) 一( ，一。) 卜x 2 ( ) 【西( ，一5 ) 一巾( 最，- 7 ) 】 - x o ( p , 一2 ) - o ( p s 一。) 】b ( ( 只一。) 一o ( 5 ) o ( g 一。) 】。 这里的s 、n 为正整数。 引理2 8 t 2 4 1m 个顶点的连通图中谱半径等于2 的图只能是q ，暑j 墨， ( 2 8 ) ( 2 9 ) ( 2 一1 0 ) ( 2 一i l ) ( 2 - i 2 ) ( 2 - 1 3 ) ( 2 - 1 4 ) p 3p 4 1 2 ：5 ，i ：7 第二章给定直径r 一2 ，刀一3 ，”一4 的谱半径第二小的树 或墨；。之一，其中只j 舄，p 2 5 3 ，# 4 7 和丑五见图2 - 5 。 上 戌= 气p 2 咖, m - 一3 2 。i。 磊= 曩， 。i。 亏= p 4巨= 壤 图2 - 5 图, l 1 2 , ：m 。- 一3 2 ，曩5 ，# l ，日；。 f i g 2 - 5 t h e g r a p h s 毋j 名三，磋，眉4 7 ，日五 引理2 9 当n 1 5 f j ，贝j m i n p ( g 4 ) ，p ( g d p ( g d p ( g d p ( g ? ) 。 证明首先令6 5 7 是从q 删除悬挂点m 后得到的图，g 5 是对g 5 7 的内路上一条边剖 分一次得到的图。显然，g 5 = 研，并且由引理2 3 和引理2 4 知， p ( 掣) p ( ) p ( 7 ) = p ( 钟) 。 接下来令g 4 7 是从钟删除悬挂点h 后得到的图，g 4 是对g 4 7 的内路上一条边剖分一 次得到的图。显然，g 4 = q ，并且由引理2 3 和引理2 4 知， p ( q ) p ( q ) p ( q 7 ) = p ( g ) 。 同样地，令g 6 7 是从联删除悬挂点一，后得到的图，g 6 是对g 6 7 的内路上一条边剖 分一次得到的图。显然，g 乡= g ，并且由引理2 3 和引理2 4 知， p ( g ) p ( g ：) p ( q 7 ) = p ( 噬) 。 为了证明结论，下面只需证明p ( 暖) p ( 掣) 。由公式( 2 6 ) 、公式( 2 8 ) 、公式( 2 - 1 1 ) 得 ( g ，x ) 一( g ，x ) = 一( p 3 ) ( 只一，) + x ( ) 【石( 只一。) 一( 一，) 】 + 参( 忍) 【x ( 只- 9 ) 一( ) ( ) 】 = 一o ( p 3 ) ( 一，) + 椰( 最) ( 一，) 一加( b ) ( 也) = 椰( 鼍7 ) 一x o ( g ) o ( p 。m ) 。 ( 2 1 5 ) 1 2 ( 2 - 1 6 ) 续剖分”一1 5 次 p ( q ) p ( q 1 5 ) 2 0 7 9 。 综上知：2 夕( q ) 2 0 7 9 。同理可证：2 p ( 霹) 2 0 7 5 。因此，得： p ( 瞬) ，p ( g ) ( 2 ，2 0 7 9 ) 。 下面约定2 x 2 0 7 9 。由公式( 2 - 1 6 ) 可得出函数列 五 ) 的特征方程为 2 一 + 。= 0 yx y 10一 +2 易发现方程的两个实根分别为： x 一7 jx + 历 y ，2 广一y z2 广一。 于是有 z ( x ) = q w + 乞硝。 因此，得到关于q ，乞为未知量的线性方程组 i q 爿5 + 乞蚝1 5 = 石，( x ) 1 q y l 6 + c 2 y 1 2 6 = 石。( x ) 。 解得： 1 3 彳5 ( x ) = x ( x 8 - 8 x 6 + 1 9 x 4 1 4 x 2 + 1 ) ， 石6 ( x ) = x 2 ( 石8 9 x 6 + 2 6 x 4 2 7 x 2 + 7 ) 。 容易发现石，( x ) 的8 个非零根分别位于下列8 个x e f 日q ( - 3 ，- 2 ) ，( - 2 ，- 1 5 ) ，( - 1 5 ，- 1 ) ，( - 1 ，- 0 1 ) ，( 0 1 ，1 ) ，( 1 ，1 5 ) ，( 1 5 ，1 9 ) ，( 2 0 9 ，3 ) 。 容易发现丸( x ) 的8 个非零根分别位于下列8 个区间 ( - 3 ，- 2 ) ，( - 2 ，一1 5 ) ，( - 1 5 ，- 1 ) ，( - 1 ，一o 5 ) ，( 0 5 ，1 ) ，( 1 ，1 5 ) ，( 1 5 ，1 9 ) ，( 2 1 ，3 ) 。 上述结论表明当2 x 2 0 7 9 时，z ，( x ) 和石。 ) 都不变号。 由于z 5 ( 2 0 1 ) oga 6 ( 2 0 1 ) 0 ，于是当2 x 2 0 7 9 时，有 z 5 ( x ) 0 且石6 ( x ) 1 得 z ( x ) 了两1 矿1 l 2 一1 ) 【似) 一聃) 】o 记 乃( x ) = z 。( x ) 一彳，( x ) ， 则有 h ( x ) = x ( x 9 一x 8 9 x 7 + 8 x 6 + 2 6 x 5 1 9 x 4 2 7 x 3 + 1 4 x 2 + 7 x 一1 ) 。 1 4 中国石油大学( 华东) 硕士学位论文 容易发现办( x ) 的9 个非零根分别位于下列9 个区间 ( - 3 ，一2 ) ，( 一2 ，一1 5 ) ，( 一1 5 ，- 1 ) ，( 一1 ，- 0 1 ) ，( 0 1 ，0 5 ) ，( 0 5 ，1 ) ，( 1 ，1 5 ) ，( 1 5 ，1 9 ) ，( 2 1 ，3 ) 。 这表明2 x 2 0 7 9 时，h ( x ) 是不变号的。既然h ( 2 0 1 ) 0 ，于是当2 x 2 0 7 9 时，有 办( x ) l ，当2 x 2 0 7 9 时，有以( x ) p f g ；5 ) 。证毕 引理2 1 0 如果n 11 且丁a ( n ，n - 4 ) ，则a ( t ) = 3 ，惕( 丁) 3 ，其中n 3 ( t ) 表示丁中 度为3 的点的个数。 证明因为d ( 丁) = n - 4 ，所以( 丁) 5 。令k i 4 是由星图k 。，。的一个悬挂点引出一 条长度为3 的悬挂路得到的图。如果4 ( 丁) 5 ，则r 必包含真子图k i 4 。 ( k i 4 ) = x 2 ( 妒一7 x 4 + 1 2 x 2 3 ) ， ( q 1 ，x ) = x ( x 2 - 1 ) 2 ( x 6 8 x 4 + 1 7 x 2 5 ) ，( 2 1 8 ) 应用m a t h e m a t i c s 直接计算得 p ( k i 4 ) 2 111 9 9 ，p ( q 1 ) 2 0 9 2 1 8 ，( 2 1 9 ) 注意到研是由q 1 对内路上的一个边剖分甩一1 1 次得到的图，于是由引理2 4 知 p ( 研) p ( k 1 4 3 ) p ( q 1 ) p ( 研) 。 这与丁的假设矛盾。因此，( 丁) = 3 。既然d ( t ) = n - 4 ，于是惕口) 3 。证毕 由n 3 ( t ) 3 可知，可以将r (