（运筹学与控制论专业论文）前三个最大特征值的3树和图类g（nm）.pdf

摘要 ；我们考虑的都是有限无向的简单连通图设9 ( n ，m ) 是所有的顶点数为佗， 边数为m 的图的集合我们讨论9 ( n ，m ) 中图的谱是指邻接矩阵a ( a ) 的谱， 图g 的谱半径p ( a ) 也是指邻接谱半径 对于非负整数尼，k 树可以这样递归的定义： 1 k 个顶点的团是k 树( k - t r e e ) ； 2 对任一南树g 加一个新点，连接它与g 中某一k 团的所有顶点，得到的 新图依然是一个k 树 树的子图称为k 部分树( p a r a a ak - t r e e ) 两个不交的图g l ，g 2 的联图g 1 v g 2 是g 1 + g 2 再加上g i 中的每一点与岛 中的所有点的连线所组成 对于所有的竹阶3 树( n 给定) ，谱半径达到最大时，图唯一确定为g 型 配v ( n 一3 ) k 1 这篇文章中，我们改善了这个结果。并给出3 树中第二，三大特 征值的图的结构 在r a b r u a l d i ，e s s o l h e i d 2 的文章中给出，对于9 ( n ，m ) 中的图g ，谱半径 达到最大时，g 含有一个星图作为它的生成子图( 即g 中有一个r , 一1 度的 点) 在这篇文章中，我们给出这样的结论：对于9 ( n ，m ) 中的所有图，当谱半 径达到最大时，最小度点的邻点必为n 一1 度的 文章中给出了以上结论的详细证明，并提出了一些在今后的研究过程中 可以进一步思考的问题 关键词：3 树；知树；谱半径；p e r r o n 向量 a b s t r a c t t h r o u g h o u tt h i st h e s i sw ec o n s i d e rf i n i t eu n d i r e c t e ds i m p l ec o n n e c t e dg r a p h s l e tg ( n ，m ) b et h es e to fa l lg r a p h sw i t hnv e r t i c e sa n dm e d g e s t h es p e c t r u mo f ag r a p hi ng ( 礼，m ) i st a k e nt ob et h es p e c t r u mo fi t sa d j a c e n c ym a t r i xa ( g ) t h e s p e c t r a lr a d i u sp ( a ) o ft h eg r a p hg i sd e f i n e dt ob et h es p e c t r a lr a d i u sp ( a ) o fa t h a ti st h em a x i m u ma b s o l u t ev a l u eo fa ne i g e n v a l u eo fa l e tak - d i q u eb ea c l i q u e 0 1 1 船v e r t i c e s f o ran o r m e g a t i v ei n t e g e rk a - t r e ei sd e f i n e di n d u c t i v e l ya sf o l l o w s ： ak - c l i q u e ( t h ec o m p l e t eg r a p h 玩) i sak - t r e e a n yg r a p ho b t a i n e df r o mak - t r e e b ya d d i n gan e wv e r t e xa n dj o i n i n gi tt oa l lt h ev e r t i c e so fs o m e 七一c l i q v eo fg i sa k - t r e e ap a r t i a lk - t r e ei sa s u b g r a p ho fak - t r e e t h ej o i ng v h o fd i s j o i n tg r a p h s o tga n dhi st h eg r a p ho b t a i n e df r o mga n dh b yj o i n i n ge a c hv e r t e xo fg t oe a c h v e r t e xo h o fa n3 - t r e e sw i t hnv e r t i c e s f i x e d ) ，t h em a x i m a ls p e c t r a lr a d i u si so b t a i n e d u n i q u e l ya tk s v ( n 一3 ) 甄w ed e f i n ei tt ob eg 1 i nt h i st h e s i s 。w er e f i n et h i sr e s u l t ，a n ds h o wt h a tt h es e c o n da n d t h et h i r dl a r g e s te i g e n v a l u ei so b t a i n e du n i q u e l ya tg 2 a n dg sr e s p e c t i v e l y h 1 【2 】r a b m a l d i ，e s s o l h e i di n v e s t i g a t e d ：l e tg 够( 仡，仃0h a v i n gt h el a r g e s t p o s s i b l es p e c t r a lr a d i u s ，t h e ng c o n t a i n sas t a ra sas p a n n i n gt r e e ( gh a sa v e r t e x w i t hd e g r e en 1 ) i nt h i st h e s i s ，w er e f i n et h i sr e s u l t ，a n dp r o v et h a to fa l lg r a p h si n 9 ( 礼，m ) ，w h e nt h es p e c t r a lr a d i u si sm a x i m a l , t h ed e g r e eo ft h en e i g h b o r so fv e f t i c e s w h o s ed e g r e ei sm i n i m a li s 扎一1 w h a t sm o r e d e t a i l e dp r o o f so ft h e s er e s u l t sa i ep r e s e n t e d a n dw eg i v es o m e i n t e r e s t i n gp r o b l e m sf o rf u r t h e r w o r k k e y w o r d s3 - t r e e ；k - t r e e ；s p e c t r a lr a d i u s ；p e r r o nv e c t o r 学位论文独创性声明 本人郑重声明： l 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经发表 或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢意。 作者签名： 日期： 学位论文使用授权声明 。本人完全了解南京师范大学有关保留、使用学位论文的规定，学校有权 保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版； 有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查 阅；有权将学位论文的内容编入有关数据库进行检索；有权将学位论文的标 题和摘要汇编出版。保密的学位论文在解密后适用本规定。 作者签名： 日期： 第1 章前言 图谱理论是图论研究中的一个重要分支我们研究图舶谱主要有以下实 际运用： 1 在量子化学里某些非饱和的碳氧化合物的键可以表示为图在这些分 子的电子的能级水平对应于图的特征值，而分子轨道的稳定性又依赖于对应 图的谱和相应的特征向量 2 可用图的谱来证明图论中的某些定理，统称为图的谱技巧( s p e c t r a l t e c h n i q u e s ) 3 由于图的谱是数值不变量的有限序列，易于计算因此可用图的谱来 计算图的某些不变量 1 1 定义和记号 定义1 图g = ( v c g ) ，e ( g ) ，惦) 。其中v c c ) 为非空点集，e ( g ) 为 与v ( g ) 无关的边集，忆一为联系g 中的边和一对无序顶点之间的关联函数 定义2g = ( x ，u ) ，h = ( y ，v ) g 与日称为同构。如果存在1 一l 映射 毋：霉翟。弘= 妒( 霉) 使对任一顶点对一，x 相应的矿= 爷( 一) ，矿= ( ) 有一a d j # = 矿a d j 则称为g 与日的一个同构，记g 垒h 表示 图g 与日同构 定义3 图的直和g l + 0 2 ：设g 1 = ( ，e 1 ) ，g 2 = ( v 2 ，l 毛) ，v t n = o ，两 个图g 1 ，g 2 的直和g l + g 2 ，其顶点集为v = u k ，其边集为e ；e i u 易 定义4 图h = ( y ) 称为图g = ( x ，u ) 的子图，如果y x ，y u 生成子图( s p a n n i n gs u b g r a p h ) ：图h = ( k v ) 是图g = ( x ，u ) 的子图， 且y = x 生成子图又称支撑子图 定义5 给定一个方阵a ，存在数量a 和非零向量x ，使a x = 从，则称a 为a 的特征值x 为a 的对应于特征值a 的特征向量 定义6 一个矩阵如果它的所有元素均是非负数，则称为非负的 为方便起见，以a 。0 表示a 为非负矩阵以a 0 表示正矩阵( 所有元 素均为正数) 图的邻接矩阵是一个非负矩阵 定义7 一个矩阵a 称为可约的( r e d u c i b l e ) ，如果存在一个置换矩阵p ， 使得p - 1 a 尸形如( 爹z 0 ) 此处，置y z 均为方阵，否则称为不可约 的( i r r e d u c i b l e ) 定义8 两个不交的图g 1 = ( ，e 1 ) ，g 2 = ( k ，j 1 2 ) 的联图g i v g 2 定义如 下： v ( g , v g 2 ) = k u 耽 e ( g i v g 2 ) = 髓u 易u e 邓：，) 旧v ( 1 ) v i ) 即g 1 v g 2 是g l + ( 毛再加上g l 中的每一点与g 2 中的所有点的连线所组 成 定义9 图g 中点 的度d g ( ) 即图g 中与点相关联的边数 j ( g ) ，a ( a ) 分别表示图g 中最小和最大的点度 定义l o 设g 是点集为 1 ，v 2 ， 的图，我们研究的图g 的谱半径 是指邻接矩阵a ( g ) 的最大特征值，记为p ( g ) a ( g ) = ( o 材) 是一个n n 阶的 矩阵( ) ，其中当地与巧相邻时( ) = 1 。否则为0 定义1 1对于非负整数k ，树可以这样递归的定义： 1 k 个顶点的团是k 树m t r e e ) ； 2 对任一树g 加一个新点，连接它与g 中某一知团的所有顶点。得到的 新图依然是一个k 树 定义1 2k 树的子图称为k 部分树( p a r t i a lk - t r e e ) 图g 的树宽度( t r e e w i d t h ) 是使得g 是k 部分树的晟小正整数k ，记为t w ( g ) = k 定义1 3a ( n ，m ) 是指所有的顶点数为n ，边数为m 的图的集合 一2 一 1 2 有关移接变形的一些引理及结论 洪渊老师在他的图谱一书中，详细介绍了移接变形的发展历程以及它在 图谱研究中的应用下面我总结了一些与我的论文相关的引理和结论 引理1 2 1 ( p e r t o n f r o b e n i u s 定理) 设a 0 不可约，则 ( 1 ) a 有一个实的正特征值r ( 最大根) 它是a 的特征多项式的单根，若九 是a 的特征根，则九i r ； ( 2 ) 对应于特征值r 的a 的特征向量为正向量； ( 3 ) 若a 有h 个模为r 的不同特征值a l ，a 2 ，h ，则九“= 1 ，2 ，h ) 是 方程妒一一l 的根； ( 4 ) 设a l ，a 2 ，a 。是复平面上的一组点则将这平面旋转0 = 鍪后，这 组点仍变为本身即a 1 口，a 2 0 ，a 。目是a l ，a 2 ，k 的某一排序； ( 5 ) 存在某一 1 使 0a 1 2 00 、 ，a ：i 。：譬0l l 00 0 a 一1 l a h l 0 0 0 此处位于主对角线上的块是方块 引理1 2 2 ( 李乔，冯克勤【1 5 】) 设口是礼阶连通图g 的任意一点，在口处分 别接出个顶点的路最和f 个顶点的路毋，记所得的图为g 则当后2f 1 ， 且p2p ( g k + 1 。l 一1 ) 时有 和 p g 。( a ) p ( g k + l ，l 1 ) 应用对任何n 阶树t 。设p ( t ) 为树t 的最大特征值，则 p ( t ) p ( 岛) = 2 c o s ( 7 r n + 1 ) 等号成立当且仅当t 鲁r 证明：若t 笋r ，贝i j a ( t ) 3 适当选择t 的度至少为3 的点反复引用 引理1 2 2 的移接变形后，得到的新树乃，则p ( 正) p ( t ) 且乃中坡至少为3 的 点数l t t 少1 按此类推，最后得到的树p 无度大于2 的点，此时t 皇r 更一般地。李冯证明了下述结果： 引理1 2 3 设钍， 是图g 的两个顶点，d ( u ，口) = m 在g 的顶点t 和 上分别接出路段、最后所得的图记为g 墨则满足下列条件之一，成立均 有p ( g 对) j p r g ( m ) l , l - i ) ( i ) m = o ，d e g ( u ) 1 ，且k z 1 ； ( i i ) m = 1 ，d e g ( u ) 2 ，d e g ( v ) 2 且k z l ； ( i i i ) m 1 ，d e g ( u ) 22 ，d e g ( v ) 2 且一z r r t , ，z 1 引理1 2 4 ( h o n g y u a n 【6 】) 设a 为实对称矩阵，p = p ( 4 ) 是a 的谱半径z 为 单位向量若z a 。= p 则a z = p x 证明：a 是一个实对称矩阵，所以a 的所有特征值均为实数，不妨令其为 a 1 a 2 h 设九对应的单位特征向量为孔f i z l 此。可表示为 n z = a l x i ， i = l ，构成n 维空间俨的标准正交基因 瓤2 = 1 i = 1 若a 1 = 沁：一k ，则命题成立否则，存在l f + 1 ，故 一4 一 z口 。：l 似 o 吼 。汹 = 船z 又已知p = x t a x 要使上式成立必须有 即 从而 a l + i 。2 = 0 口 当图g 连通，则邻接矩阵a ( g ) 是不可约的，f 1 p e r r o n - f r o b e n i u s 定理( 引 理1 2 i ) 存在唯一的正的单位向量我们称这样的向量为p e 哟n 向t ( p e r r o n v e c t o r ) 下面这个引理是我们这篇论文中用到的最主要的引理 引理- 1 2 5 ( b a o f e n gw u ，e n l ix i a o ，y u a nh o n g 【3 】) 设u ，口是n 阶连通图g 的任意两个顶点，s 为某一正整数若 口l ，t j 2 ，) n a ( v ) l v g ( 乱) 非空 _ r z = ( z l ，x 2 ，z 。) t 是g 的p e r r o n 向量，其中魏对应于顶点地( 15i 祀) 将g 中的边v v i 替换为u l j i ( 1 s ) 得到r a g * ( 如图1 2 1 所示) 若z 。， 则p ( g ) z t a ( g 扣= 以g ) 若p ( c ) = p ( g ) ，则 p ( a ) = x t a ( g ) z 从n a ( g + ) z = p ( 1 ：y ) = p ( g ) z = a ( g ) z 由a ( g 扣= p ( c 净知 由a ( g 净= p ( g 净知 p ( c ) z a = ( a ( g + 净h = 饥e ，g 扣) 0 p ( c ) x v = ( a ( g ) z ) ”= z 。= 戤+ z p v , e n o ( v )v , e n o * 扣) i = 1 甄= p ( c + ) z 。= _ ( g ) z 。 “n o ( 口) 因为p ( g ) 1 产生矛盾，所以，p ( g ) y t , 1 i e n ：若不然，则地蜘，由引理1 2 5 舞l p ( g ) p ( g ) ，矛盾 口 推论1 2 2 设e = 伽是t t 阶树丁的一条边，t e 的每个分图至少有两个 顶点将边e 收缩为点u ，并将一个新的孤立点t t ，连接u ，所得到的图记为r 。 贝l j p ( t ) p ( t + ) 从引理1 2 5 可以看出：对连通图将p e r r o n 分量较小的点 的邻接点 往p e r r o n 分量不小于该分量的点移接时，谱半径严格增大，如果新的图仍 图i 2 2 然连通，这样的移接进行下去这样可以求得某些连通图类中谱半径达到最大 的极图 反之，将p e r t o n 分量较大的点的邻接点往p e r r o n 分量较小的点上移，谱半 径可以增大，也可以变小 例： 、望芝! ：2 “ p = 1 9 0 2 1 谱半径变大 谱半径变小 图1 2 3 p = 1 8 0 1 9 第2 章前三个最大特征值的3 树 2 1 引言和引理 衡量图复杂性的一个重要的标准是树宽度( t r e e w i d t h ) 对于树宽度的 定义有很多种，我们给出的是依据a m b o r g 和p r o s k u r o w s k i 8 给出的定义 对于非负整数k ，k 树可以这样递归的定义： 1 k 个顶点的团是树( k - t r e e ) ； 2 对任一k 树g 加一个新点，连接它与g 中某一k 团的所有顶点，得到的 新图依然是一个k 树 k 树的子图称为k 部分树( p a t i n ak - t r e e ) 图g 的树宽度( t r e e - w i d t h ) 是使 得g 是k 部分树的最小正整数也记为t w ( g 1 = 七 洪渊老师曾给出【5 1 这样的结论：如果图g 的树宽度为k 。那么 p ( g ) k - 1 + v 4 k n - 7 ( k + 1 ) ( 3 一k - 1 ) z 当且仅当g 垒j v 一女) 硒时等号成立 在洪老师结论的基础上，文章( h a i x i ny u 。j i n s o n gy u a n , y u a nh o n ga n dj i n - l o n gs h u 【7 1 ) 中给出关于2 树的结论：对于所有竹阶的2 树( n 给定) ，谱半径达到 最大时图唯一确定，为- i 皇尬v ( n 一2 ) 硒，同时给出了第二，三大特征值时 图的结构，分别表示为马，凰对于n 7 ，玩，日2 ，玩如图2 ，1 1 所示 痧移 图2 i i 这一章我们希望给出的是关于3 树的相关结论，在证明过程中主要用到的 是第1 章第2 小节中引理1 2 5 ( b a o f e n gw u ，e n l ix i a o , y u a nh o n g 【3 】) 的移接变形 的思想以及弓i 理的变形，下面是我们所需要的引理变形 引理2 1 1 ( h a i x i ny u ，j i n s o n gy u a n ，y u a nh o n ga n dj i n l o n gs h u 【7 】) 设( 札， ) ，g ) 是佗阶连通图g 的任意两条不相邻边，s 为某一正整数 若v l ，啦，) ( u ) n g ( ) n a p ) n g ( 口) 非空且d g ( 地) = 2 ，岳= 扛l ，z 2 ，$ 。) r 是g 的p e r t o n 向量，其中瓤对应于顶点陇( 1 i n ) 将g 中 的边( 札，v i ) ，( t ，q ) 替换为0 ，v i ) ，( q ，仇) ( 1 i s ) 得到图g 若z 。+ z 。x p + z p 贝o p ( a ) x t a ( g ，+ ) z ，a ( g ) z 2 p ( g ) 若o ( a ) = p ( g ) ，则 p ( g + ) = x t a ( a ) z 从i 币a c c ) z = p ( g ) z = p ( c ) x = a ( c ) x 由a ( g ) z = p ( a ) z 知 p ( g + ) z 。= ( a ( g + ) z h = 乏二 z t v i e n a ( u ) 由a ( g = p ( c ) x 知 p ( g ) 气= ( a ( g ) z ) 。= z 。= 勋+ ；戤；p ( c ) z u = p ( g ) $ ” n ( 曲 n i 为p ( g ) 1 产生矛盾所以，p ( g ) p ( c + ) 命题得证 口 一9 一 由证明过程我们知道，对于引理2 i 1 中只需保证 口l ，v 2 ，) n e ( u ) n n c ( v ) n g o , ) u n g ( q ) ，而他们是否有除了乱，口，p ，g 之外的公共邻点， 对于结论的证明并无影响，从而我们得到下面的引理2 1 2 引理2 1 2 设( u ，t j ) ，0 ，q ) 是n 阶连通图g 的任意两条不相邻边，s 为 某一正整数若 1 ，抛，) g a ( u ) n g ( 口) g ( p ) u g ( g ) 非空且z = ( x l ，x 2 ，) r 是g 的p e r r o n 向量，其中翰对应于顶点陇( 1 i n ) 将g 中 的z l ( u ，地) ，( ，地) 替换为，仇) ，( 口，地) ( 1 i 8 ) 得到图p 若z 。+ 唧+ 。g ， 则p ( g ) 3 ) 但此时d g ( 口) = 3 ， 且口与口2 ( 或”1 ) 不相邻，所以g 依然至少有两个不相邻的顶点，且它们的度 为3 。 综合以上1 ，2 可知，结论成立 口 2 2 前三个最大特征值的3 树 洪渊老师曾给出【5 】这样的结论：如果图g 的树宽度为。那么 粥)k-1型+v4罨kn-囹(k+1)(3k-1) 当且仅当g 岂v m k ) k 1 时等号成立 所以对于所有的几阶的3 树m 给定) ，图k 3 v ( n 一3 ) 蜒时谱半径达到最大， 我们定义它为g 1 后面我们给出了第二。第三大特征值时图的结构，分别表示 为g 2 ，g 3 对于n 8 时，g l ，g 2 ，g 3 如图2 2 1 所示 圆画 g l g 2g 3 图2 2 1 如果图g 是n 阶1 拘1 3 n ( n 5 ) 。通过令不等式( 1 ) 中七= 3 ，我们可以得 n p ( g ) 1 + 丽= 百，等号当且仅当g l 鲁k 3 v ( n 一3 ) 炳时成立下面我们一 步步改善这个结果，得到了3 树达到第二，第三大特征值时的图的结构，主要进 展在下面证明过程当中 定理2 2 1 设g 是礼阶的3 树( 佗6 ) ，1 1 g 喾g 1 ，n a p ( c ) p ( g 2 ) ，当且仅 当g 兰g 2 时等号成立 证明：如果某些耳4 有共同的尬，而且这些耽中余下的点均为3 度点，我们 称这些尬具有性质p 如果共同的k 3 为三角形( ， ，叫) ，我们称这些确具有性 质p ( u ， ，叫) 设t ( g ) o t ( c ) n 一4 ) 是具有性质p 的甄的最大数 假 设6 1 ，如，况( g ) 具有性质p ( u ， 3 ，叫) ，且其余点为 l ，抛，v t ，那么d g ( v i ) = 3 ( i = l ，2 ，t ) 因为( 1 t ( c ) 几一4 ) ，所以g 中至少有一个致不在6 1 ，如，5 t ( a ) e o ， 而且1 r 4 有一个点度为3 不失一般性，我们假设这些心为a l ，2 ，。 ( 1 8 t ( g ) ) ，具有性质p 0 ，q ，r ) ，且其余顶点为w 1 ，w 2 ，- 一，蛾 ( 1 s t ( g ) ) 设z = ( 。l ，z 2 ，) t 是g 中的p e r r o n量，其中孔对应 于顶点地( 1 i n ) 1 如果三角形( 缸，口，t l ，) 与如，吼r ) 无公共顶点，我们考虑下面两种情形： 情形l ：钆+ + z 口酃+ + x r 去除边( p ，硼1 ) ，( q ，w 1 ) ，( r ，叫1 ) ，且 加边( 乱，t j 1 ) ，( t ，w 1 ) ，蜘1 ) ，我们可以得到一个新的3 树g ，显然g 7 有t ( c ) + 1 个凰具有性质p ( u ， ，加) ，g t ( g ) = t ( g ) 4 - 1 由引理2 1 3 知，p ( g ) p ( g ，) 情形2 ：茹。+ z 。+ 。口 x p + a 口+ z ，去除边( 钍，饥) ，0 ，仇) ，( 硼，v d ( i = l ，2 ，t s + 1 ) ，且加边( p ，砘) ，( 口，地) ，( r 地) 0 ；1 ，2 ，t s + 1 ) ，那 么我们得到一个新的3 树g ，显然g ，有t ( c ) + 1 个尬具有性质尸0 ，玑r ) ，且 t ( g ，) = t ( g ) + 1 由引理2 1 3 知，p ( c ) p ( g ，) 由情形i ，2 知，由引理2 1 3 利用移接变形，我们总可以得到一个新的3 树g ：， 满足p ( c ) p ( g ：) l i t ( c ；) = t ( g ) 4 - 1 2 如果三角形( 让，口，t l ，) 与也，g ，r ) 有一个公共顶点，设叫= n 则我们只需比 较钆+ 鼠与劫+ 的大小，考虑以下两种情形： ， 情形l ：z 。+ 霉。x p + x q 去除边0 ，t ，1 ) ，( q ，w 1 ) ，且加边( ，w 1 ) ，( ， 1 ) ，我们 可以得到一个新的3 树g ，显然g 7 有t ( c ) + 1 个玩具有性质p ( t ， ，伽) ，i ；t t ( g ) = t ( g ) + 1 由引理2 1 2 知，p ( a ) p ( g ，) 情形2 ：钆+ 昂+ z q 去除边( u ，仇) ，( u ，v d ( i = l ，2 ，t s + 1 ) 。 且加边，仇) ，( g ，) 0 = 1 ，2 ，t 一8 + 1 ) ，那么我们得到一个新的3 树g ，显 然g ，有t ( g ) 4 - 1 个玩具有性质p q ，r ) ，i l t ( g ) = t ( c ) 4 - 1 由引理2 1 2 知， p ( g ) p ( g ”) 由情形l ，2 知，由引理2 1 2 利用移接变形，我们总可以得到一个新的3 树g ：， 满足p ( c ) p ( g ；) 且t ( g ：) = t c c ) + 1 3 如果三角形( 让，t ，叫) 与( p ，q ，r ) 有两个公共顶点，设 = q ，w = r ，则我们 只需比较z 。与酃的大小由引理1 2 5 ，类似地利用移接变形，我们总可以得到一 个新的3 树佛，满足p ( g ) _ p ( g ：) 且t ( g ) = t ( c ) + i 如果t ( g ) + 1 n 一5 ，则对于g ：重复以上的步骤，直至达到具有性 质p 的段的数目为n 一5 所以我们得到一系列3 树g ；，g ，g ；，而且有 p ( g ：) p ( g ；) p ( g ；) 另外，t ( g 知1 ) = ( g ：) + 1 ( i = 1 ，2 ， 的，且g ：掣g 2 从而结论成立 k 一1 ) 且t ( c 1 ) = 1 7 , 一5 这时，g ；是唯一 口 定理越2 设g l ，g 2 都是n 阶的3 树6 ) ( 如图2 2 2 所示) 那么p ( g 2 ) p ( c o 。包 g 1g 2 证明：设z = ( x l ，x 2 ，z 。) r 是g 2 中的p e r r o n 向量，其中z i 对应于顶 点地( 1 is 扎) 假设g 2 中佗一5 个肠具有性质p ( 札，口，伽) ，对应的尬中的其 他点为。l ，t j 2 ，v n 一5 假设施= ( 乱，口，w ，t ) 和( 4 = ( t ，8 ，w ，) 有公共的三角 形( 牡，硼，t ) 情形l ：z 。祝去除边( s ，t ) 并g 1 j n 边( s ，口) ，这样我们得到图g 1 所有 的g 1 中的确具有性质p ( u ， ，叫) ，而且( g 1 ) = n 一3 由引理1 2 5 知，p ( g 2 ) p ( a o 情形2 ： z 。 规 去除边( ，”1 ) ，( t ，口2 ) ，( ，- 5 ) ，并且加 边( t ，) ，( ，也) ，( t ，一5 ) ，这样我们得到图g 1 所有的g l 中的玩具有性 质p ( u ，t ，彬) ，而且t ( g 1 ) = 几一3 由引理1 2 5 知，p ( c 2 ) p ( c 1 ) 由上面的情形知，结论成立 口 筑2 章前+ 个最j 、彳j l 施的3 树 推论2 2 1 设g 是竹阶的3 树( n 5 ) ，n a p ( a ) p ( a 1 ) 当且仅当g 掣 g 1 时，等号成立换言之，对于所有的n 阶的3 树( 其中n 是给定的) ，谱半径达到最 大时，图的结构唯一是g l 皇k 3 v ( n 一3 ) 硒 洪渊老师曾给出f 3 】这样的结论：如果图g 的树宽度为k ，那么 p ( g ) k 一- 1 + v 互4 k n 李- ( k 圃+ 1 ) ( 3 k - 1 ) 当且仅当g 型k v ( 佗一七) 鲍时等号成立我们知道推论2 2 1 从另一角度给出 了k = 3 时图g 的结构 定理抛3 设g 是礼阶的3 树m 8 ) ，g 喾g z j l g 箬g 2 n a p ( c ) p ( ( 毛) ， 当且仅当g 兰g a 时等号成立 一 圆5 抛固 g 4 地国锄圆5 图2 2 3 证明：类似于定理2 2 1 的证明，我们只需比较t ( g ) = n 一6 时的所有3 树 的谱半径的大小而对于所有的t ( g ) = 竹一6 的3 树，我们可以证明，在同构意义 下，这样的3 树只有四种情形( 即t ( g ) = 仃一6 ( i = 3 ，4 ，5 ，6 ) ) 如图2 2 3 所示 g 2 同样参照定理2 2 1 的证明过程，我们知道t ( g ) = n 一5 时图唯一确定为g 2 从g 2 出发，要使得t ( g ) 降为n 一6 ，可以从t l ，忱，u 3 的公共邻点集中找出一点 记为蛳，破坏它和这三个点的邻接关系，即具有性质p 篚j k 4 减少一个( t ( g ) 从n 一 5 降为n 一6 ) 但是，我们还要保证所得到的新图仍然属于3 树这个类，不能破 坏其余的3 度点。t 1 6 的三个新邻点只能在钍l ，u 2 ，中选择，且这三个点组 成飓易知，c g = 1 0 种，分析以下情形： 情形1 u l ，u 2 ，u 3 不满足条件，t ( c ) = n 一5 ； 情形2 钍l ，地，锄；t 2 ，u 3 ，u 4 抛，u 4 ，u 5 均不满足条件三个点无法组成尥， 与3 树的定义矛盾； 情形3 对于其余的6 种情况：( a ) u 1 ，抛，u s ；c o ) v a ，u 3 ，u s ；( c ) u l ，i t 3 ，u 4 ； ( d ) 钍l ，u 3 ，u s ；( e ) 让1 ，“4 ，u s ；( f ) 如，u 4 ，u s ；由同构的定义易证，( a ) 与( b ) 同构， ( e ) 与( d 同构 。 综合以上的三种情形，在同构意义下，所有的满足条件t ( g ) = n 一6 的3 树 共有4 种情形：g j ，g 4 ，g 5 ，g 6 ，如图2 2 3 所示 下面我们证明以下结论 结论1 p ( g 4 ) p ( g z ) 结论1 的证明：设z = ( x l ，x 2 ，) t 是g 4 中的p e r r o n 向量，其中觑对 应于顶点忱( 1 i n ) 比较分量2 ：4 ，x 5 ：如果肌奶我们可以去边( 蛳，粕) ，同 时加边( 札5 ，t 6 ) ，从而得到图g 3 由引理2 知，p ( g 4 ) z 5 ，我们 可以去边( u s ，坳) ，同时加边( u 4 ，乱2 ) 。从而得到图g 3 由引理2 知，p ( g 4 ) p ( g 3 ) 国 结论2 p ( g 5 ) p ( g 3 ) 结论2 的证明：设z = l ，z 2 ，) r 是g 5的p e r r o n 向量，其中甄对应 于顶点忱( 1 l n ) 比较分量z l ，z 2 ：如果2 $ l ，我们可以去边( 钍2 ，) ，同时 加边( 钍1 ，) ，从而得到图g 3 由引理2 知，p ( g s ) z l ，我们可以 去边( u 1 ，u 4 ) ，同时加边( 2 ，毗) 。从而得到图g 3 由引理1 2 5 知，p ( c 5 ) p ( c 3 ) 结论3 p ( g e ) p ( g 3 ) 结论3 的证明：设z = ( z 1 ，观，x , 0 r 是g 6 中的p e r r o n 向量，其中以 对应于顶点地( 1 i 佗) 比较分量z 3 ，x 4 ：如果有0 4sz 3 ，我们可以去 边( 蛳，) ，同时加边( 坳，讹) 。从而得到图g 3 由引理1 2 5 知，p ( c 6 ) x 3 ，我们可以去边( 撕，t ，1 ) ，( u 3 ，t j 2 ) ，( u 3 ，一6 ) ，( ，u 2 ) ，同时 加边( m ，t ，1 ) ，( 蛳，t j 2 ) ，( 蛳，一6 ) ，( 蛳，抛) ，从而得到图g a 由引理1 2 5 知， p ( g o ) p ( c a ) 由以上的三个结论，我们可以证明定理2 2 3 成立 口 第3 章图类9 ( n ，m ) 中的谱半径 3 1 ；引理 我们考虑的都是有限无向的简单连通图设孚( n ，m ) 是所有的顶点数 为礼t 边数为m 的图的集合宅e a ( n ，m ) 中，所有的最小度为6 的图的集合记 为9 ( 行，仇，6 ) 显然，g ( n ，m ，6 ) 9 ( 凡，m ) 例如，督( n ，m ，1 ) 是指所有顶点数 为n ，边数为m ，最小度为l 的图我们讨论g ( 几，m ) 中图的谱是指邻接矩 a ( g ) 的谱，图g 的谱半径p ( c ) 也是指邻接谱半径 本章讨论的是有关于图类9 ( 凡，仇) 中的谱半径。我们在前人工作的基础 上给出更广泛，更一般的结论这一章中主要用到的是图谱研究中移接变形 的重要思想，同时还用到了下面这些引理以及一些前人已有的结论， 引理3 1 1 限a b r u a l d i ，e s s o l h e i d 4 ) 对于岔( n ，m ) 中的图，当谱半径达 到最大，g 含有一个星图作为它的生成子图 引理3 1 五j f i n c k ，g g m h m a n n ) 设g i 为n i 阶n 正则图 = 1 ，2 ) ，则 娜删= 勰训a _ r 2 ) 咄他】 附注：g i 是n i r i 正则图( i = 1 ，2 ) ，g 1 v g 2 并不一定正则 3 2 图类9 ( n ，m ) 中的谱半径 在r a b r u a l d i ，e s s o l h e i d 4 文章中给出，对y - g ( n ，m ) 中的图g ，谱半 径达到最大时，g 含有一个星图作为它的生成子图( 即g 中有一个n 一1 度的 点) 在这个结论的基础上。我们给出了更广泛的结果 定理3 2 1 对于孚( n ，m ) w ( n ，m ，1 ) 中的所有图，当谱半径达到最大时，最 小度点的邻点必为n l 度的 证明：( 反证法) 对于g ( n ，m ) 中谱半径达到最大的图g ，它的最小度点是 假设结论不成立，即存在点z n ( v ) ，且点z 的度小于n 一1 ，从而图g 中存 在点u ，使得u 岳( 回，考虑到d ( u ) d ( 口) 且z ( ) v ( 牡) ，必存在点y ( u ) ( 口) 我们比：较p c r r o n 向量中，点t ，u 对应的分量大小由引理1 2 5 通过 移接变形，必可以得到谱半径比g 更大的图g ，而且顶点数和边数均未发生 变化，又因为6 2 ，保证了口是连通图，即新图g + 9 ( n ，m ) 够( 礼，m ，1 ) ，与 假设矛盾，从而结论成立 口 由引理3 1 1 知，对于毋( n ，m ，1 ) 中的图，必有一个n 一1 度点再结合定 理3 2 1 ，我们得到这样的结果： 定理3 2 2 对于蛋( 竹，m ) 中的所有图，当谱半径达到最大时，最小度点的 邻点必为n 一1 度的 在定理3 2 2 这样的结论，在许多比较图类9 ( n ，m ) 时，可以从一个新的角 度，更简单快捷的判断下面以n - - 6 为例，给出一个图来判断他们的最大特征值 的大小 g ( 6 ，1 5 ) = m 1 ； 6 ( 6 ，1 4 ) = m 2 ； g ( 6 ，1 3 ) = ，m 4 ； g ( 6 ，1 2 ) = 地，慨，m r ，m s ，m 9 ) 对于尬，m 2 来说，所在图类就只有他本身，即自身就是达到谱半径最大 而同时我们也看至4 ， 氟，m 2 中最小度点的邻点确实都是n 一1 度的 对于9 ( 6 ，1 3 ) 来说，该图类有两个图坞，m 4 ，但m 4 的最小度点的邻点并不 满足都是r , 一1 度的，而地符合该条件，所以图类9 ( 6 ，1 3 ) 中，图飓达到谱半径 最大 对于g ( 6 ，1 2 ) 来说，该图类有五个图坛，m 6 ，m r ，m 8 坞但m 7 m 8 m 9 的 最小度点的邻点都不