（运筹学与控制论专业论文）几类图的谱.pdf

摘要 本文中我们主要考虑一般简单连通无向图的谱，包括二类特殊图类的 邻接谱和一般简单连通无向图的l a p l a c e 谱具体结果如下： 1 对已有的移接变形方法进行改进，刻画了邻接谱半径达到第二大， 第三大的n m 2 ) 阶2 树 2 研究了直径为2 的图及其一类子图，分别刻画出其邻接谱半径达到 最大时的极图，并对极图的谱半径上界进行估计 3 利用图的度平方和的不等式，得到一般简单连通无向图的l 印l a c e 谱半径的一个新上界： 邸) 等+卜z ) 掣刊n 一( 墨) 2 等式成立当且仅当g 为星图硒一l 关键词：移接变形，谱半径，l 印l a c e 谱半径，2 一树，度序列 1 l a b s t r a c t i nt h j 8p 印e r ，w em a i l l l y8 t u d yt h es p e c t r u mo f8 i m p l ec o n n e c t e du n d i r e c t e dg r a p 上l s ，i n d u d i n gt h e8 d j a c e n c ys p e c t r u ma i l dt h el 印l a c es p e c t r u m s o m er e s u l t 8w i l lb e 舀v e ni nt h j 8t h e s i s 1 b yu s i n gt h ei m p r 0 、谢m e t h o do fg r a f tt r a l l 8 f o r m a t i 。n ，w ec l l 盯a c - t e r i z et h e2 一t r e e st h a tm a x i m i z et h es e c o n da n dt h et h i r dl a r g e s ta d j a c e n c y 8 p e c t r a lr 8 d i u s 2 w bs t u d yt h ef 8 p l l sw i t hd i a m e t e r2a n do n ec l a s so ft h e i r8 u b f 印h sa 1 1 dc h a r a c t e r i z et h ee x t r e m a lf a p h sw h 0 8 ea d j a c e c ys p e c t r a lr a d i u 8 i st h el 舡g e s ti nt h e 8 et w oc l a 8 8 e s ，r e s p e c t i v e l y m o r e o v e r ，w eg e tt h eu p p e r b o u n d sf o rt h e8 p e c t r a lr a d i io ft h e s ee ) ( t r e m a lg r 印 l s 3 b yu s i n gt h ei n e q u a l i t i e 8o nt h es u mo ft h es q u a r e so ft h ed e g r e e s o fag r a p h ，w eg e tas h a r pu p p e rb o u n df o rt h el a p l a c es p e c t r a lr a d i u 8o f 8 i m p l ec o n n e c t e du n d i r e c t e dg r 印1 1 8 ： 邸) 各+f 。) 掣啊一( 墨) 2 e q u a l i t yh o l d 8i fa n do n l yi fg i ss t a rg r 印hk 1 ，n l k e yw o r d s ： g r 甜tt r a n s f o r m a t i o n ，s p e c t r dr a d i u s ，l a p l a c es p e c t r a lr a d i u s d e g r e es e q u e n c e ，2 一t r e 朗 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的 研究成果。据我所知，除文中已经注明引用的内容外，本论文不包含其他 个人已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和 集体，均已在文中作了明确说明并表示谢意。 作者躲俞爝昕隰川f 2 莎 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有 权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质 版。有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书 馆被查阅。有权将学位论文的内容编入有关数据库进行检索。有权将学位 论文的标题和摘要汇编出版。保密的学位论文在解密后适用本规定。 学位论文作者签名： 葑擂口印 导师签名： 日期：旧6 ，蔓6 日期： 州堂叼 f 第一章概述 图论是一门应用广泛的数学分支，是处理离散数学问题的强有力的工 具五十年代开始，随着计算机科学、信息科学、系统科学与运筹学的发 展，人们越来越重视图论及其应用的研究近年来，无论从本身的理论价值 还是实际应用的广度和深度来看，图论及其应用的研究正处于蓬勃发展的 新时期图论的研究内容及其独特的研究方法，随着现代科技的不断进步， 越来越显示其独特的作用和魅力 图谱理论是图论中的一个相当重要，也是非常活跃的研究方向，它的研 究与发展有着重要的理论和实际意义它不仅促进和丰富了图论和组合数 学本身的研究，而且在量子化学、物理、计算机科学、通信网络及信息科 学中均有广泛的应用近年来关于图谱的论文在期刊杂志上陆续涌现，一系 列关于图谱理论的专著【2 ，5 ，7 ，1 2 】不断丰富和促进着这门学科的发展 1 1 基本概念 本文所研究的图均为无环、无重边、有限无向的简单连通图设图 g = ( k e ) ，其中矿为顶点集，y = y ( g ) = 1 ，u 2 ， 。) ，i y i = n 称为图 g 的阶数，e 为边集，e = e ( g ) = e 1 ，e 2 ，e 。) ，l 刀l = m 为图g 的边 数若e 的两个端点分别为顶点u 与 ，记为e = ( u ，u ) = “u ，称顶点 与 相邻接，记为u 一u ；否则称它们不相邻接，记为u ”若边( u ，u ) e ， 则称缸或者 与e 关联与同一个顶点关联的两条边称为相邻接；否则称 为不相邻接与 关联的边的个数称为 的度，记作d 。( ) = 巩图g 中 最大、最小的顶点的度分别记为( g ) 和6 ( g ) ，图g 的度序列就是由g 的各顶点的度为元素的序列，通常按不增的顺序写作( d 1 ，d 2 ，矗) ，其中 d d 2 蟊g ( u ) 表示顶点 在图g 中的所有邻点所组成的集合 顶点的2 一度是与魄相邻接的点的度之和，用= q 。“由表示称差 为地的平均度，用m 表示记妮( q ) = u 码。( ) ，则i 孵池) i 如 图g 的邻接矩阵记为a = a ( g ) = ( o d ) 。，是一个n 阶的( o ，1 ) 一方 阵，其定义如下： 铲 ：戮 显然，= 0 ，= ，故而a ( g ) 是一个实对称方阵我们称d e t ( a j a ) 为图g 的特征多项式，记为p ( g ) 或p ( g ；a ) 它的特征值a l ， 2 ，k 均 为实数，不妨将其由大到小排列为 l a 2 a 。根据a ( g ) 的定义， 我们有沁= o ，a ；= d = 2 m 这些特征不以顶点标号顺序的不 同而改变，我们记九( g ) = 九( a ) = 九( = l ，札) ，称 s p e c g = a 1 ( g ) ，k ( g ) ，k ( g ) ) 为图g 的邻接谱，或记为 鼢c g = ( m 翟，m 蓉。，m 这里a 1 a 2 九，m ( 九) 为九的重数显然，f m ( 凡) = n 扛= l 一般性，我们称a 。( g ) 为图g 的邻接谱半径，在不致混淆的情况下， 简称为图g 的谱半径，通常记为p ( g ) 当图g 连通时，a ( g ) 是一个非负 不可约矩阵，根据矩阵论的知识( p e r r o m n o b e n i u s 定理) 【2 3 】，p ( g ) 为单 根，并存在一个单位正特征向量z = ( 。，。，z 。) t 与p ( g ) 相对应，即 日 o ，a ( g ) 茁= p ( g ) 。，其中以对应于顶点仇( i = 1 ，n ) 称z 为a ( g ) 的p e r r o n 向量，简称g 的p e r r o n 向量 2 p e r r o n n o b e n i u s 定理设b 是n 1 ) 阶不可约非负方阵，记 p ( b ) = m l 入1 i ，l 2 i ， a 。1 ) 其中 a l ， 2 ，a 。) 是b 的n 个特征值， 则 ( 1 ) p ( b ) 是口的特征值； ( 2 ) p ( 口) 作为b 的n 2 个元素的函数是严格递增的，即若有b e ，g b o ，则p ( e ) p ( b ) ； ( 3 ) p ( 曰) 是口的单根； ( 4 ) b 有正特征向量= 与p ( 日) 相应，即日z = p ( 口) 2 而且b 的任一 非负特征向量定是z 的正整数倍 若以d ( g ) 表示图g 的顶点度构成的对角矩阵，即d ( g ) = d t 叼 d 1 ，如， ，厶，则图g 的l a p l a c e 矩阵定义为l ( g ) = d ( g ) 一a ( g ) 由定义可 知l ( g ) 是对称半正定方阵且每一行的行和为零，所以。是( g ) 的最小特 征值l ( g ) 的特征值全体可如下表示： s p e c ( l ( g ) ) = p 1 ( g ) ，p 2 ( g ) ，p 。一l ( g ) ，p 。( g ) ) 称为图g 的l a p l a c e 特征位或l 印l a c e 谨其中 p 1 ( g ) p 2 ( g ) - - p 。一l ( g ) p 。( g ) = o 称p 1 ( g ) 为图g 的l a p l a c e 谱半径，通常用p ( g ) 表示根据工( g ) 的定 义，我们有m = 吨；2 m ，p ? = 哦( d + 1 ) 这些特征也不以顶 点标号顺序的不同而改变 给定图g = ( k e ) 若y y ，e 一 u u e i u ，”矿) ，则称图 g = ( y ，e 7 ) 是g 中由矿导出的子图，记g 为g 】，称为g 的导出子 图导出子图g y ， 记为g y ，它是从g 中删除中的顶点以及 与这些顶点相关联的边所得到的子图若= ”) ，则把g 一 ) 简记为 g 一廿 3 此外，还有些未给出的专业术语与记号将分别在文中的相关章节里给 出或参阅 3 ，7 】在不致引起混淆的情况下，上面的记号b ( ) ，a ( g ) ，p ( g ) 等可将g 省略，相应地记为( ) ，a ，p 等 1 2 本文主要内容 为了清晰起见，现将本文的主要结论陈述如下，其中定理和图的编号同 后面一致，部分记号的含义到相应部分再作介绍 1 在第二章中，我们推广了移接变形，并利用移接变形对谱半径的影 响，对谱半径第二大、第三大的n m 2 ) 阶2 - 树作出了刻画 定理2 2 3g 为n 阶连通图，( 钍，u ) ，( p ，g ) 是g 的不相邻接的两条边 设 l ，砚，) ( 1 s l g ( 牡) n g ( 口) i ) 是点集g ( t ) n g ( ) ( g ( p ) u g ( g ) ) 的子集，茁= ( 。l ，z 2 ，z 。) t 是g 的p e r r o n 向量，其中q 对应于 顶点仉( 1 n ) 将g 中的边u 饥，伽i 替换为边p ，q ( 1 t s ) 得 到图驴若z 。+ 唧+ z q ，则p ( g ) ) 阶自一树，那么当 = 2 时，在n m 2 ) 阶2 树中谱半径最大的2 _ 树为图2 1 _ 1 中的g 1 本文进一步研究了n m 2 ) 阶2 一树，当n = 5 或n = 6 时，我们可以 按照谱半径的大小很容易地对5 阶和6 阶2 树进行排序当n 7 时，进而 刻画出了谱半径第二大、第三大的2 _ 树，即图2 1 1 中的g 2 和g 3 痧 g 1 4 g 2g 3 图2 1 1 2 在第三章中，我们研究了直径为2 的图及其一类子图，分别刻画出其 邻接谱半径达到最大时的极图 定理3 。2 1 若g g = g l g 为件阶简单连通图且直径为2 ) ，g 的最小度为6 ，t 为g 中度为j 的点，则p ( g ) p ( g - o ) 等式成立当且仅 当g 竺g l o g 1 0 形如图3 2 1 所示，其中g 1 0 的导出子图g 1 0 u 为完全图 峨一1 ，和完全图k ，一l 中的d 个顶点邻接 图3 2 1 g 】o 定理3 3 1 若g 尹，y ( g ) ，d 缸= d l ( ，= g i g 9 ，且存在 “y ( g ) 使得( ) 为独立集) ) ，则p ( g ) p ( g 1 1 ) 等式成立当且仅当 g 兰g 1 1 g 1 1 形如图3 3 1 所示，其中g 。( u ) 为独立集，g 1 1 的导出子图 g ，- 心，。( 札) u 是完全图k 。一- 一d ，a 。( u ) 中的每个顶点和虽。( u ) 中 的每个顶点邻接 ) t 上) 图3 3 1 g 1 1 通过对g 1 0 ，g ，结构的分析，利用引理3 12 对这两类图的谱半径上界 5 进行估计 定理3 2 2图g 1 0 的谱半径满足不等式 概) 生幽卫雩匠受匝 等号成立当且仅当g 1 0 为完全图 定理3 3 2 当1 ；时，图g ，t 的谱半径满足不等式 愉) ) 阶树对于特殊情况= 2 ，谱 半径第二大，甚至第三大、第四大的n m 2 ) 阶二树具有怎样的结构 呢? 本章来研究这个问题在本章中我们解决问题的主要手段是移接变形 2 1引言及主要引理 图的复杂度的度量中的一个重要概念就是树宽度许多n p - h a r d 的问 题，例如找最大的点独立集，计算色数及哈密顿圈等问题，如果树宽度有界， 那么这些问题都可以用线性算法解决关于树宽度有很多等价的定义，下面 给出a r n b o r g 和p r 0 8 k u r o w s k i 【1 1 ( 或见【1 1 1 ) 提出的概念 树的递归定义：团( 即完全图j “) 是树从七团加上一个新点连 接k 团中所有点得到的+ 1 团是树，如果g 是树，则加上一个新点 连接g 中的某一个团得到的图也是女树 树的子图称为部分树 图g 的树宽度是使得g 是部分k 树的最小正整数膏，记为细( g ) y h o n g 1 8 】得出，如果t 叫( g ) = 七，则 p ( g ) 生生丝譬婴型! 刿， 其中等号成立当且仪当g 兰讯v ( n 一) 西也就是说，谱半径最大的树 为虬v m 一七) k 1 那么当= 2 时，在n m 2 ) 阶2 一树中谱半径最大的 为j 如v 一2 ) 蹈，即图2 1 1 中的g 1 本章中我们利用另外一种方法重额 证明此结论，并在此基础上继续研究n ( n 2 ) 阶2 树利用移接变形的方 法对谱半径第二大、第三大的2 一树作出刻画，得到如下结果： 7 当n = 5 或礼= 6 时，我们可以按照谱半径的大小对5 阶和6 阶2 树 进行排序当n 7 时，n 阶2 树中谱半径第二大、第三大的分别是图2 1 1 中的g 2 、g 3 嗲移移 g 2 图2 1 1 为了方便起见，先将本章需要的主要引理陈述如下 引理2 1 1 【2 8 l 给定实对称矩阵4 及单位向量z 舯，设 1 是 a 的最大特征值若 1 = z t a z ，则z 是a 1 所对应的单位特征向量，即 a o = a l z 引理2 1 2f 19 】多项式p ( g ；a ) 和p ( 毋a ) 分别表示图g 和h 的特 征多项式如果当a p ( 日) 时p ( g ；a ) p ( 日) 2 2移接变形的推广 1 9 7 9 年，李乔和冯克勤在文章【2 2 】中证明移接变形结论该结果自发表 以来，不断被其它文献引用，在图谱理论中发挥着越来越重要的作用， 定理2 2 1 【2 2 】设n ， 是图g 的两个顶点， ， 之间的距离d ( u ，u ) = m 。在g 的顶点札和口上分别接出路鼠，最后所得的图记为g 鼹则以 下任一条件成立均有p ( g 镀) p ( g 嚣；h ) ( i ) m = 0 ，d 。( u ) 1 ，且f 1 ，此时即u = ； ( i i ) m = l ，d g ( “) 2 ，d 。( ) 2 且z 1 ； 8 ( i i i ) m 1 ，d o ( t ) 2 ，d 。p ) 2 且七一2 m ，f 1 随后，很多学者对移接变形进行了深入的研究，得到了许多新的结果 【3 0 ，3 3 ，3 5 1 丰富和扩充了原来的李冯移接变形2 0 0 3 年吴宝丰在他的硕士 论文【3 2 】中给出了另外一种形式的移接变形用于图的邻接谱的研究 定理2 2 ，2 【3 2 】设u ，口是连通图g 的任意两个顶点，s ( 1 s d 。( ) ) 为某一正整数若 ，地，) 虬( ) 。( t ) 非空且z = ( 。1 ，观，。) r 是g 的p 咖向量，其中甄对应于顶点q ( 1 i n ) 将g 中的边 饥替换为u 弘( 1 i s ) 得到图g 4 若z 。，则 p ( g ) o 于是比较( 2 2 ) 和( 2 3 ) 式，得p ( g + ) z 。 p ( g ) z 。，即 p ( g + ) p ( g ) ，与假设矛盾所以p ( g ) 4 ) 阶2 一树成立令g 是一n 阶2 一树，那么 存在一n 一1 阶2 - 树g ，g 是由g 7 加上一个新点 并且连接 和g 7 的两个邻接顶点得到的由归纳假设g 有两个不邻接的顶点 l ，忱 且如，( 1 ) = d g ，( 忱) = 2 如果 既不和 l 邻接也不和 2 邻接，那么 如( ”1 ) = d g ( 2 ) = 2 且在g 中”1 和吨不邻接，结论成立如果 和”1 邻 1 0 接但不和址邻接，那么d 。( ) = d 。池) = 2 且在g 中 和忱不邻接，结论 成立类似可得u 和地邻接但不和 1 邻按时结论成立因为在g 7 中蜘和 v 2 不邻接，所以 不能既和v 。邻接又和也邻接综合以上情况，定理得证 为了证明过程中叙述问题方便，这里给出一些记号 在礼阶2 一树g 中，如果一些三角形有同一条公共边，并且这些三角形 中除这条公共边上的两点外另一点均为2 度点，我们称这些三角形具有 性质p 如果这条公共边是( 札，口) ，我们称这些三角形具有性质p ( u ， ) 设 f ( g ) 为2 一树g 中具有性质p 的三角形的最大数目我们有如下定理 定理2 3 。2 设g 为礼阶2 树且g 喾g l ，则p ( g ) p ( g 2 ) 等号成立 当且仅当g 皇g 2 ( g l ，g 2 见图2 1 1 ) 证明： 因为g 喾g 1 ， ( g 1 ) = 礼一2 ，所以l f ( g ) n 一2 设这f ( g ) 个三角形分别为以，如，画( g ) ，它们的公共边为( u ，u ) 这些三角形中除 u ，口点外另一点分别为 1 ，吨，研( g ) ，且始池) = 2 ( i = 1 ，2 ，f ( g ) ) 即这f ( g ) 个三角形具有性质p ( u ， ) 因为g 菩g - ，所以g 至少有 一个三角形不是6 1 ，如，m 中的某一个，并且这个三角形中有一个 2 度点不妨设三角形- ，2 ，。( 1 s f ( g ) ) 有同一条公共 边( p ，q ) ，并且这些三角形中除p ，q 两点外另一点均为2 度点，设这些 点为”1 ，吡，啡( 1 s f ( g ) ) 即三角形l ，2 ，。具有性质 p ( p ，g ) 令z = ( z l ，勋，z 。) r 是g 的p e h d n 向量，其中就对应于项点 婊( 1 i n ) 下面分情况讨论 情况l 边( u ， ) 和，q ) 不相邻接 情况1 az 。+ 唧+ 将g 中的边( p 1 ) ，( 口，1 ) 替换为 ( u ，叫1 ) ，( ，训1 ) 得到一个新的2 一树g ，则d 有f ( g ) + 1 个三角形有性 质p 沁，) ，故f ( g ，) = z ( g ) + 1 由定理2 2 3 可得p ( g ) p ( g ，) 情况1 bz 。+ 唧+ 。q 将g 中的边( “，吡) ，( u ，地) 替换为 ( 弘地) ，( 口，仇) “= l ，2 ，f ( g ) 一s + 1 ) 得到一个新的2 - 树g ”，则g ” 有z ( g ) + 1 个三角形有性质p ( p l q ) ，故f ( g ”) = f ( g ) + 1 由定理2 2 3 可得 p ( g ) p ( g ”) 情况2 边( u ， ) 和扣，口) 相邻接设 = p 则只需比较和z 。由 定理2 2 2 移接变形的方法可褥到一个新的2 - 树g ”满足p ( g ) p ( g ) ， 且? ( g ) = f ( g ) + 1 或者f ( ) = z ( g ) + 2 以上两种情况说明，对任一2 一树g 喾g 。，经过移接变形后，一定存在 2 - 树口，l ( 口) = f ( g ) 十1 或者f ( g + ) = f ( g ) + 2 ，并且p ( g ) p ( 口) 因此如 果 ( g ) + l n 一4 ，对p 重复以上的过程直到具有性质p 的三角形的最大 数目达到n 一4 在这个过程中得到的二树的谱半径是递增序列，而有竹一4 个三角形共用一条公共边的2 - 树是唯一的，它同构于g 2 所以对n 阶2 树 g 喾g l ，有p ( g ) p ( g 2 ) ，等号成立当且仅当g 竺g 2 对z ( g 。) = f ( g ) + 2 的情况可类似证得由此定理得证 这样我们确定了谱半径达到第二大的2 _ 树，下面我们用移按变形的方 法再一次证明p ( g 2 ) p ( g 1 ) ( g 1 ，g 见图2 1 1 ) 定理2 3 3 若g l ，g 2 为图2 3 ，1 中的n m 5 ) 阶2 一树，则p ( g 2 ) p ( g 1 ) ， 证明：令z = ( z 1 ，。2 ，z 。) t 是g 2 的p e r r o n 向量，其中孔对应于 顶点地( 1 i 扎) g 2 有n 一4 个三角形共用一条公共边且这些三角形的 另一点均为2 度点，设这条公共边为( t ，“) ，这n 一4 个三角形的另一点分别 为 l ，比，- 4 令三角形t “ 和三角形t s 的公共边为( t ，u ) 1 2 钞i 莎 g 1 图2 3 1 情况l 若z 。将g 2 中的边( ，s ) 替换为边( ，8 ) ，得到2 - 树g 1 此时g 1 中的所有三角形有性质p ( t ，u ) ，并且f ( g 1 ) = n 一2 由定理2 2 2 ， p ( g 2 ) p ( g 1 ) 情况2 若髫。 z 。将g 2 中的边( u ， 1 ) ，( u ，u 2 ) ，( u ，u 。一4 ) 替换为 边( ， 。) ，( ，地) ，( ，u 。一4 ) ，得到2 一树g 1 此时g 1 中的所有三角形有性 质p ( t ， ) ，并且z ( g 1 ) = n 一2 由定理2 2 2 ，p ( g 2 ) p ( g 1 ) 综合以上两种情况，定理得证 通过定理2 3 2 和定理2 3 3 ，我们得到nm 5 ) 阶2 一树中谱半径达到 最大和第二大的极图分别是g 1 和g 2 那么很明显对于5 阶2 _ 树有下列推 论 推论2 3 4 所有5 阶2 一树在同构意义下只有两个图日l ，日2 ( 如图2 3 2 所示) ，显然p ( 飓) p ( 皿) + q 图2 3 2 下面我们继续寻找n 阶2 一树中谱半径达到第三大的极图当n = 6 时 1 3 ：守兰 刃协固 f 4 j j 图2 3 ，3 证明：首先证明“f 5 ) p ( f 4 ) 令。= ( z l ，z 2 ，。6 ) t 是f 5 的 p e n 伽向量，其中筑对应于顶点地( 1 6 ) 如果。1 。2 ，将r 中的 边( 吨，v 3 ) 替换为边( ，t 1 3 ) ，得到2 一树f 4 由定理2 2 2 ，p ( r ) _ d ( 乃) 如 果口1 z 2 ，将民中的边( 1 ，地) 替换为边( 2 ，啦) ，得到2 _ 树毋由定理 2 2 ，2 ，p ( f 5 ) p ( n ) 因此p ( 曩) p ( r ) 其次证明p ( f 4 ) p ( f 3 ) 令p ( 日；a ) 和p ( 玛；a ) 分别表示毋，b 的特 征多项式通过计算得p ( r ；a ) = a 8 9 ”一8 a 3 + 9 a 2 + 8 a 一1 ；p ( 毋； ) = a 6 9 a 4 8 3 + 9 a 2 + 6 a 一4 显然，当a ，( f 4 ) 2 时p ( b ；a ) p ( 丑；a ) 由引理2 1 2 ，p ( 蜀) p ( 玛) 再次证明p ( b ) p ( b ) 令z = ( 铂，z 2 ，) t 是玛的p e r r o n 向量， 其中以对应于顶点仇( 1 i 6 ) 如果。4 巧5 ，将局中的边( l ，) 替换 为边( 1 ，蛳) ，得到各树咒由定理2 2 ，2 ，p ( b ) p ( f 2 ) 如果z 4 $ 5 ，将焉 中的边( 3 ，地) 替换为边油，如) ，得到2 坤9 毋由定理2 2 2 ，p ( f 3 ) p ( 忍) 1 4 因此p ( 玛) p ( f 2 ) 显然p ( f 2 ) p ( f 1 ) ，定理得证 当然，我们可以直接算 导这五个图的谱半径分别为：p ( f 1 ) = 3 3 7 2 3 ， p ( f 2 ) = 3 2 8 1 4 ，p ( 足) = 3 2 3 6 1 ，p ( 毋) = 3 2 2 2 7 ，p ( 毋) = 3 1 8 1 9 同样得到 p ( r ) p ( 日) p ( 玛) p ( f 2 ) p ( r ) 定理2 3 7 设g 为n 7 ) 阶2 树，g 菩g 1 ，g 喾g 2 ，则p ( g ) p ( g 3 ) 等号成立当且仅当g 型g 3 ( g 3 见图2 1 1 ) 证明：根据定理2 3 2 的证明，我们只需比较下列n 7 ) 阶2 一树( 如 图2 3 - 4 所示) 的谱半径，其中f ( g t ) = n 一5 0 = 3 ，4 ，5 ，6 ) ，f ( q ) = 扎一6 0 = 7 ，8 ，9 ) g 3 我们先来证明一些论断 论断1 p ( g 4 ) p ( g 3 ) t h 一5 1 5 图2 3 4 令z = ( z l ，z 2 ，。) r 是g 4 的p e r r o n 向量，其中妣对应于顶点 ( 1 i n ) 如果z l z 2 ，将g 4 中的边( 地，) 替换为边( u 1 ，抛) ，得 到2 一树g 3 由定理2 2 2 ，p ( g 4 ) p ( g 3 ) 如果。1 z 2 ，将g 4 中的边 ( 1 ，铀) 替换为边( 地，地) ，得到2 一树g 3 由定理2 2 2 ，p ( 翻) p ( g 3 ) 因此 p ( g 4 ) p ( g 3 ) 论断2 p ( g 5 ) p ( g 3 ) 令嚣= ( 观，正2 ，z 。) 7 是g 5 的p e r r o n 向量，其中鼢对应于顶点 娥( 1 t n ) 如果。3 勋，将g 5 中的边( u 1 ，址) 替换为边( ”l ，嘶) ，得 到2 - 树g 3 由定理2 2 2 ，p ( g 5 ) p ( g 3 ) 如果z 3 2 ，将g 5 中的边 ，地) 替换为边( 忱，啦) ，得到2 树g 3 由定理2 2 2 ，p ( g 5 ) p ( g 3 ) 因此 p ( g 5 ) p ( g 3 ) 论断3 p ( g 6 ) p ( g 3 ) 令z = ( z l ，z 2 ，) 7 是g 6 的p e r m n 向量，其中甄对应于顶 点轨( 1 i n ) 如果。z n _ 2 ，将g 6 中的边( 一2 ，u 。一3 ) 替换为边 ( 一3 ，) ，得到2 树g 4 由定理2 2 2 ，p ( g b ) p ( 6 f 4 ) 如果z 。 嚣。一2 ，将 g 6 中的边( ， 1 ) ，( ，吨) ，( ，一5 ) 替换为边( 一2 ， 1 ) ，( 。一2 ，t j 2 ) ， ( 一2 ，一5 ) ，得到2 一树q 由定理2 2 2 ，p ( g 6 ) p ( g 4 ) 由论断l ，p ( g 4 ) p ( g 3 ) ，因此p ( g 6 ) p ( g 3 ) 论断4 p ( g 7 ) p ( g 3 ) ， 令z = ( z l ，z 2 ，z 。) 7 是g 7 的p e r r o n 向量，其中q 对应于顶点 耽( 1 t 竹) 如果z 1 。4 ，将g 7 中的边，啦) 替换为边( u l ，地) ，得 到2 - 树g 3 由定理2 2 2 ，p ( g 7 ) p ( g 3 ) 如果。1 z 4 ，将g 7 中的边 ( 1 ，也) 替换为边( 2 ，m ) ，得到2 一树g 3 由定理2 2 2 ，p ( g 7 ) p ( g 3 ) 因此 p ( g 7 ) p ( g 3 ) 论断5 p ( g 8 ) p ( g b ) 】6 令石= ( z 1 ，石2 ，) r 是g 8 的p e r r o n 向量，其中观对应于顶点 地( 1 i 礼) 如果茁2 轧，将g 8 中的边她，m ) 替换为边，蝴) ，得到 2 坤目g 4 由定理2 2 2 ，p ( ( 珀) p ( ( h ) 如果z 2 ，将g 8 中的边( l ，忱) 替换为边( u 1 ，弛) ，得到2 - 树g 4 由定理2 2 2 ，p ( g 8 ) p ( 瓯) 由论断1 ， p ( g 4 ) p ( g 3 ) ，因此p ( g 8 ) p ( i 锡) 论断6 p ( g 9 ) p ( g 3 ) 令z = ( z l ，茹2 ，) t 是g 9 的p e r m n 向量，其中甄对应于顶 点地( 1 i n ) 如果。z 。一5 ，将g 9 中的边( 一2 ，u 。5 ) 替换为边 ( 一2 ，) ，得到2 树g 3 由定理2 2 2 ，p ( g 9 ) p ( g 3 ) 如果。 z 。一5 ，将 g 9 中的边( ，口1 ) ，( ，地) ，( ，一8 ) 替换为边( u 。_ 5 ，啦) ，( _ 5 也) ， ( - 5 一8 ) ，得到2 _ 树g 3 由定理2 2 2 ，p ( g 9 ) p ( g 3 ) 因此p ( g 9 ) 2 ) 阶简单连通图的集合为9 ，即9 = g l g 为n 阶 简单连通图且直径为2 ) 定理3 2 1 若g 9 ，g 的最小度为d ，u 为g 中度为6 的点，则 “g ) p ( g 1 0 ) 等式成立当且仅当g 望g 1 0 g l o 形如图3 2 1 所示，其中 g 1 0 的导出子图g 1 0 一为完全图k 。一1 ，“和完全图一。中的6 个顶点邻 接 】8 图3 2 1g l o 证明：设u 的邻域为( “) = 如1 ， 2 ，) 在满足g 的直径为2 的前提下，反复应用引理3 1 1 ，在y u ) 中的顶点之间加边使由顶点 集y u ) 导出的子图成为完全图珞- 1 记加边后得到的图为g t o ，则 p ( g ) p ( g l o ) 等式成立当且仅当g 笺g l o 引理3 1 2 告诉我们，当一个图只有三种度时，可以估算出这个图的谱 半径的上界通过对g l o 结构的研究，我们发现它是一个三度图，故我们得 到g 1 0 的谱半径的一个可达上界 定理3 2 2 图g 1 0 的谱半径满足不等式 p ( g 。) 生生近兰颦磐兰型监型，( 3 1 ) 等号成立当且仅当g 1 0 为完全图j 厶 证明：设图g l o 的废序列为( d 1 ，d 2 ，“) ，其中d l d 2 d n 情况1l 6 n 一1 此时d 1 = d 2 = = 如= n 一1 ，d 6 + l = d d + 2 = = 如一l = 礼一2 ，如= 6 因为札一l n 一2 ，由引理3 1 2 ， p ( g 。) 生盐迹旦坠墅! l 二业坐i 型坠兰望 一6 1 + ( d + 1 ) 。+ 4 ( n 一1 6 ) ( n 一2 ) 一 2 】9 情况26 = n 一1 此时g l o 为完全图，p ( g 1 0 ) = n 一1 ，验证 得( 3 1 ) 式中等号成立 综合以上两种情况，定理得证 根据洪渊老师得到的谱半径的可达上界：当g 是简单连通图时， p ( g ) 丽i i 再1 ，其中等式成立当且仅当g 为完全图或者星图 k 1 n - l 【1 5 】我们再次对图g i o 估计p ( g 1 0 ) 的上界 g - o 的边数m 满足2 m = 一1 ) j + 一2 ) 一1 6 ) + 6 = ( n 1 ) ( n 一 2 ) + 2 6 ，所以 p ( g l o ) ( n 1 ) ( n 一3 ) + 2 6 ，( 3 ，2 ) 且等号成立当且仅当g ，o 为完全图k 。 当6 = l 或d = n 一1 时，( 3 1 ) 式中的上界和( 3 2 ) 式中的上界两者 相等当1 6 礼一l 时，生二生上z 堕里三二! 箬2 二l 1 丛型 l ，则p ( g ) p ( g 1 1 ) 等式成 立当且仅当g 兰g 1 1 g 1 1 形如图3 3 1 所示，其中g 。( u ) 为独立集，g 1 1 的导出子图g ， 心。( u ) u ) 】是完全图一l d ，a 。( “) 中的每个顶点和 嵋，( t ) 中的每个顶点邻接 “) ) 图3 3 1g 1 1 证明：在满足g 芦的前提下，反复应用引理3 1 1 ，在2 ( “) 扣 = y ( ( u ) u u ) ) 中的顶点之间加边，使由顶点集2 ( u ) u ) 导出的子图 成为完全图一。一d ，记加边后得到的图为g l l ，则p ( g ) p ( g 1 1 ) 等式成立 当且仅当g 型g 1 1 g 1 1 的结构表明它也是。个三度图，所以运用引理3 1 2 ，我们得到在特 定条件下g l l 的谱半径的上界 定理3 ，3 2 当1 昙时，图g ，。的谱半径满足不等式 p ( g 。，) 坚生生塑! 警坐生坚型( 3 4 ) 证明：设图g 。，的度序列为( d ，d 2 ，d 竹) ，其中d - d 2 如， 则d l = d 2 = = d n 一1 一d = 礼一2 ，g 1 l 的另外两种度分别是札一d 和d 通 过比较n d 和d 的大小，得到在不同情况下p ( g 1 1 ) 的上界 情况l 若n d d ，即d 昙，则d 。一d 一如一d + 1 = = “一1 = 扎一d ，d 。= d ，由弓l 理3 1 2 ， ，( g 1 1 ) g 二! 迎亚雯正辜巫至至婴 1 d l + 品匕i f j 而f 1 甄干可犷两 2 等式成立当且仅当礼一2 = 他一d = d ，即n = 4 ，d = 2 ，所以g 1 1 垒a 情况2 若n d ；，则如一d = d ，如一“，= d n d + ：一= 矗= n d ，因为n d d ，由引理3 1 2 ， 愉) o 时，上式等式 成立当且仅当g 是星图尬一i 或完全图或完全图和一个孤立点的并 k 。一lu 硷；当g 是连通图时，上式等式成立当且仅当g 是星图k 1 ，l 或 完全图厩 ( 2 ) 2 0 0 3 年k c d 鹪对毋的可达上下界做了大量研究 = 】 定理4 1 2 【9 】2 m + 1 ) 一m ( 1 + p ) ，其中p = 【辅，表 = 1 示不超过。的最大正整数等式成立当且仅当g 是几乎正则图( 如果g 的 任意两个顶点的度至多差一，则称g 为几乎正则图) 定理4 1 3 【9 】当g 是连通图时， 2 m 一礼( n 一1 ) 矗+ 2 m ( 矗一1 ) l = 】 等式成立当且仅当g 是星图玛一1 或正则图 的 砑 。 定理4 1 4 【9 l 喜 m ( 是z ) - d z ( 各一- 一岩) ， 其中d 1 是g 的最大度，m 1 是具有最大度的点的平均度等式成立当且仅 当g 是星图尬一，或完全图j 厶或空图n j 对于n 阶树来说，霹的这个上界总比d c b e n 的上界好 4 2对l a p l a c e 谱半径上界的改进 图的l a p l a c e 谱半径是图论研究的一个重要方面，关于l a p l a c e 谱半径 的上界已有很多结果本节中，先给出与图的度序列有关的l a p l a c e 谱半径 的若干上界，再得到一有所改进的上界 ( 1 ) 1 9 9 7 年j s l i 和x d z h a i l g 给出了个下面两个关于度序列的 l 拄p l a c e 谱半径的上界 定理4 2 1f 2 l 】若g 为n 阶连通图，g 的度序列为d 1 d 2 如， 则 p ( g ) 2 + 、( d 1 + d 2 2 ) ( d l + d 3 2 ) ， 等式成立当且仅当g 为正则二部图或者路p 3 或者路p 4 定理4 2 2 2 1 】记r = m o z 也+ 巩：u u ) ，设z ，口y ( g ) 且 也+ 也= r ，另记s = m n z 如+ d 1 ：“ e ( g ) 一z f ) 则 p ( g ) 2 + 、p 一2 ) ( s 一2 ) 2 0 0 2 年潘永亮( y b n gl i a i l gp a n ) 【27 证明了上式等式成立当且仅当g 为正则二部图或者半正则二部图或者路只 ( 2 ) 2 0 0 1 年j s l i 和y l p a n 应用定理4 1 1d c a e n 的不等式给出了 与图的顶点的度及顶点数n ，边数m 有关的l a p l a c e 谱半径的几个上界 2 4 定理4