（运筹学与控制论专业论文）关于变换图的若干性质.pdf

摘要 近年来，陆续有学者对包括全图在内的变换图进行了研究，也取得了不少成果，如变 换图满足连通性的充要条件，变换图的直径与原图直径的关系等等但是由于到目前为 止，针对变换图的研究成果还较少，因此，对于变换图的性质还有很大的研究空间基于这 样的背景，我们针对变换图的正则性和谱半径进行了一系列的研究，并利用图的移接变形 理论得到了一类特殊图的全图的谱半径上界，具体结论如下： 1 满足正则性的八类变换图的原图可分别刻画如下： 图g + + + 及g 是正则图当且仅当g 是正则图g + + 一和g 一+ 为正则图的充要条 件是g 为g 、k 2 。一2 或j “g + 一+ 和g 一+ 一是正则图当且仅当g 为c s 、k t 、k j 、恐3 或 g o ，其中图g o 如图1 所示g 一+ + 和g + 是正则的当且仅当g 是盐 正则图 2 八类变换图的谱半径分别有如下之上界( 其中几表示图g 的顶点数，m 表示图g 的边数) ： ( 1 ) p ( g + + + ) 2 r a n - i - 3 m - n 24 - 1 ( 2 ) p c c + + 一1 v 1 4 m n n 2 5 m + 1 ( 3 ) p ( g 一+ + ) 以而二丽= 爵町 ( 4 ) p ( a 一+ 一) v 7 4 r a n - 9 m - n + 1 ( 5 ) p ( g + 一+ ) 、m 拿+ 断n 一2 n + 1 ( 6 ) p ( g + 一一) 、，；元趸_ j = - 芝再磊f ：- 互再f = - 互元。：f i ( 7 ) p ( g 一一+ ) 、m 2 + , n 2 + 2 m 一3 n + 1 ( s ) p ( g ) 舻+ n 2 + 2 r a n 一6 r a 一3 n + 1 3 在第四章我们证明了在所有树的全图中星图的全图是谱半径唯一达到最大的 关键词：移接变形，谱半径，树，星图，全图，变换图，半正则二部图 5 a b s t r a c t r e c e n t l y8 0 m es c h o l a r ss t u d yt r a n s f o r m a t i o ng r a p h sa n dp r e s e n tal o to fr e s u l t s i ns u c c e s s i o n - - t h es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o no fc o n n e c t e dt r a n s f o r m a t i o ng r a p h s ， f o re x a m p l e b yn o w ，r e s u l t so ft r a n s f o r m a t i o ng r a p h sa l el e s s t h u st h e r ea r ea k t p r o p e r t i e so ft r a n s f o r m a t i o ng r a p h sd e s e r v i n gt os t u d y a n dt h e nw es t u d yr e g u l a ra n d s p e c t r a lp r o p e r t i e so ft r a n s f o r m a t i o ng r a p h s ，a tt h es a m et i m e ，w ep r e s e n ta nu p p e r b o u n do i ls p e c t r a lr a d i io ft o t a lg r a p h so ft r e e s t h ec o n c l u s i o n sa l e8 8f o l l o w s ： 1 t h er e 目, l a r i t yo ft r a n s f o r m a t i o ng r a p h s ( c h a p 2 、： ( 7 + + + a n dg a r e r e g u l a ri fa n do n l yi fg i sr e g u l a r ；( + + 一a n dg 一一+ a l er e g u l a r i fa n do n l yi fg 垒! g o r k 2 n 一2 0 r k 4 ；g + 一+ a n dg 一+ 一a l er e g u l a ri fa n do n l yi fg 垒 g o r k 7 0 r k 2 0 r k s ，3 0 rg 0 ( s e e g r a p h l ) ；g - + + a n d g 降一a x er e g u l a r i f a n do n l y i f g i 8 孚一r e g u l a r 2 s o m eu p p e rb o u n d so nt h es p e c t r a lr a d i u so ft r a n s f o r m a t i o ng r a p h s ( i nc h a p 3 ， ni 8t h en m n b a ro fv e r t i c e si ng ，mi st h en u m b e ro fe d g e si ng ) ： ( 1 ) p ( g + + + ) 、2 m n + 3 m - n 2 + 1 ( 2 ) p ( g + + 一) 4 m n - n 2 - 5 m + 1 ( 3 ) p ( a 一+ + ) 撕而i 丽= ；耳1 ( 4 ) p ( g _ 一) 钥而再面再丽 ( 5 ) p ( g + 一+ ) 、m 2 + 6 r n - 2 n + 1 (6)p(g+一一)、，rn2+2mn-2m-2n+1 ( z ) p ( c 一+ ) k ，m ( k ) 为的重数显然，m ( 知) = n 例如：完全图玩的邻 接谱可表示为 s 一= ( n ：1l 。) 一般性，称入1 ( g ) 为图g 的邻接谱半径，在不致混淆的情况下，简称为图g 的谱半 径，通常记为p ( g ) 当图g 连通时，a ( g ) 是一个非负不可约矩阵，根据矩阵论的知识， p ( g ) 为单根，并存在一个单位正特征向量z = 扛1 ，茁2 ，) 与p ( g ) 相对应，即孔 0 ，a ( g = p ( g ) 。，其中戤对应于顶点仉a = 1 ，哟称z 为a ( g ) 的p e r r o n 向量，简 称g 的p e r r o n 向量 给定图g = ( k 功若矿v ，e ，= 聊昱心t 矿) ，则称图g ，= ( ，) 是g 中由y 生成的子图，记茭j g v ，】 以下是本论文中最为重要的三个概念： 定义1 1 1 如果图g 是一个二部图，即v ( g ) = u ，m n k = 0 ，( ) ，似2 ) 都是 空图如果中顶点的度都相等，k 中顶点的度也都相等，则将该二部图g 称为半正则 二部图 定义1 1 2 【3 4 l 图g 的全图t ( g ) 构造如下：t ( g ) 的顶点集y ( r ( g ) ) = v ( g ) u 第一章：引言华东师范大学硕士论文 3 e ( g ) ，边集 e ( t ( g ) ) = e ( g ) u ( u ，e ) j “y ( g ) ，e e ( g ) ，t 一e ) u ( e “c 2 ) le 1 ，e 2 e ( g ) ，e l e 2 ) 定义1 1 3 7 1 设g = ( g ) ，e ( g ) ) 是一简单图，z ，y ，z 都是只取+ 或一的变量 变换图g 。舻以v ( v ) ue ( g ) 为其顶点集，且对任意的q ，p y ( g ) ue ( g ) ，a 和p 在 图g w 。中邻接( 或关联) 的条件如下： ( i ) o ，pey ( g ) z = + 时当且仅当口和p 在图g 中邻接；z = 一时当且仅当口和卢在 图g 中不邻接 ( i i ) a ，卢e ( g ) 暑= + 时当且仅当a 和卢在图g 中邻接；y = 一时当且仅当a 和p 在 图g 中不邻接 ( i i i ) 口y ( g ) ，p e ( g ) z = + 时当且仅当。和p 在图g 中关联；z = 一时当且仅 当o l 和卢在图g 中不关联 此外还有些未给出的专业术语与记号将分别在文中的相关章节里给出或参阅在不 致引起混淆的情况下，上面的记号可将g 省略，如a 、p 等 第一章：引言华东师范大学硕士论文4 1 2本文主要内容 1 在第二章中主要通过对变换图的基本参数的分析讨论，刻画了正则变换图的原图 应满足的充要条件，得到以下的结果： 定理2 2 1 若图g 是n ( 2 ) 阶简单图，图g + + + 及g 是正则图当且仅当g 是正 则图 定理2 。2 2 设g = ( g ) e ( g ) ) 是珏( 2 ) 阶简单连通图，有m 条边，则g + + 一 和g 一+ 为正则图的充要条件是g 为c ；、j g 。一2 或局 定理2 2 3 设图g 是n ( 2 ) 阶简单图，有m 条边，则g + 叶和g 一+ 一是正则图当且 仅当g 为侥、玛、鲍、焰3 或g 0 ，其中图g 0 如图1 所示 定理2 2 4 设图g 是礼阶简单连通图，有m ( 1 ) 条边，则g 一+ + 和g + 一是正则的 当且仅当g 是盐正则图， 2 在第三章中主要讨论的是变换图的谱性质我们结合前人关于变换图连通性的结 果，将已知的一些图的谱半径上界及研究方法应用于交换图，得到了变换图谱半径上界的 初步结果以下是第二章的主要结论 引理3 1 1 对于任意给定的图g ，则有 ( 1 ) 图g + + + 连通当且仅当g 连通 ( 2 )图g + + - 连通当且仅当g 至少有两条边且g 不是2 k 2 ( 3 ) 图g 一+ + 都是连通的 ( 4 ) 图g 一+ 一连通当且仅当g 不是星图 ( 5 )图g 降- + 连通当且仅当图g 不含有孤立点 ( 6 ) 图g + 一连通当且仅当图g 至少含有两条边 ( 7 ) 图g 一十都是连通的 ( 8 )图g 连通当且仅当g 既不是星图也不是恐 引理3 2 1 设g 是一简单连通图，有n 个顶点m 条边，a 是图g 的邻接矩阵则 p ( a ) 、2 m 一竹+ 1 ， 且等号成立当且仅当g 星图或完全图 引理3 2 2 设n 阶图g 的顶点度序列为d l 如d ，i ，则p ( g ) 、：1 霹 第一章：引言 华东师范大学硕士论文5 定理3 2 3 设g 是n ( 3 ) 阶简单连通图，有m 条边，则 p ( g + + + 、 、2 m n - i - 3 m - n 2 + 1 定理3 2 5 设g 是n ( 2 ) 阶简单连通图，有m ( 2 ) 条边，r g 不是2 鲍则 p ( g + + 一) v 4 m n - - n 2 - - 5 m + 1 定理3 2 7 设g 是n ( 3 ) 阶简单连通图，有m 条边，则 p ( g 一+ + ) 、，哐鬲鬲亍= j 再f = 丽 定理3 2 9 设g 是n ( 2 ) 阶简单连通图，且g 不是星图，有m 条边，则 p ( g 一+ 一1 、 4 m n - 9 m - n + 1 定理3 2 1 1 设g 是嚣( 3 ) 阶简单图，有t n , 条边_ r g 中无孤立点，则 p ( c + 一+ 1 q m 2 + 6 m - 2 n + 1 定理3 2 1 3 设g 是礼阶简单图，有m ( 2 ) 条边且g 中无孤立点，则 p ( g + 一) 、，舻+ 2 r a n 一2 m 一2 n + 1 定理3 2 1 5 设g 是n ( 3 ) 阶简单图，有m 条i 盘i g 中无孤立点，则 p ( g 一+ ) m 2 + n 2 + 2 m - 3 n + 1 定理3 2 1 7 设g 是n 阶简单图，有仇条边r g 中无孤立点，同时g 既不是j ，也 不是星图，则 p ( g 、 2 ) 阶简单图，图g 卅及g 是正则图当且仅当g 是正 则图 证明由表1 知，对任意顶点 y ( g ) ，d g + + + ( = 2 d e ( v ) ；对g 的任意一条边e = u w e ( g ) ，其中“，叫y ( g ) ，都有如+ 十+ ( e ) = d a ( u ) + d g ( 加) 若g + + + 是正则图，则d g ( 口) 均相等，所以g 也是正则图 反之，若g 是r 正则图，则d g + + + ( ) = d g + + + ( e ) = 2 r ，即图g + + + 是2 r 正则的 又g + + + = ( g ) c ，g 是正则的当且仅当g + + + 是正则的，由此得证一 定理2 2 2 设g = ( g ) ，e c g ) ) 是n ( 2 ) 阶简单连通图，有m 条边，则g 叶+ 一和 g 一+ 为正则图的充要条件是g 为g 、k 2 。一2 或j “ 证明注意到g 一+ = ( g + + 一) c ，g 一+ 为正则图当且仅当g 牛+ 一是正则的因此只要 考虑图g + + 一即可 先证必要性若g 牛+ 一是正则图，根据表1 知对任意一条边伽j e ( g ) ，都有d c ( u ) + d g ( w ) + n 一4 = m ，即 d g ( + d g ( 硼) = f n 一竹+ 4 ( 1 ) 下面根据g 的正则性分两种情况进行讨论 情况1 若g 是一个r 正则图则 2 r = m 一佗+ 4 = 要一n + 4 z 所以4 r = w 一2 n + 8 ，即( r 2 ) 一4 ) = 0 ，故n = 4 或r = 2 考虑到g 的连通性，r = 2 只 可能是g 皇c k 而n = 4 的正则连通图只能是a 或j 矗由此必有g 岂c k 或g 兰k 4 情况2 若g 不是正则图对g 中任意二顶点v o 和t ，且u 如，根据g 的连通性，从 点珈到点笤总有一条最短路k 。长度为d g ，影) 由( 1 ) 式即知所有使德始( 蛳，u ) 为 偶数的点口的度都为如( 如) 而所有使得d g ( 咖，t ，) 为奇数的点 的度都等于m 一竹+ 4 一 d a ( ) 即可对v c g ) 作一划分：v ( v ) = uk ，nk = 0 ，其中= 扣i 锄 v c g ) 日- d c ( v o ，u ) 为偶数) ，k = 扣lu v ( c ) l d g ( v o ，。) 为奇数) 中的点在g 中的 第二章：变换图的正则性 华东师范大学硕士论文 9 度都相等，k 中的点在g 中的度也都相等而( h ) ，( ) 一定是空图，否则由( 1 ) 式得g 为 正则图由此可知此时g 是一个半正则二部图 不妨设h 中的点在g 中的度为 k 中的点在g 中的度为s ，且r 8 又设lhl - n l ，iki = n z ，有m + m = n 接下来再分两种子情况进行讨论 子情况2 1 若g 是完全二部图，则r = 砌，s = n 1 根据( 1 ) 式有 r + s = m n + 4 = n l r n + 4 ， 即 n = n x n 2 一n + 4 = n 1 一n 1 ) 一n + 4 ， 由此得前一加l + 2 一2 ) = 0 ，即n 1 = 2 或n 一2 ，所以g 皇k 2 一2 子情况2 2 若g 不是完全二部图，则必有r 2 由( 1 ) 式得 1 言n s 也s = m = r + s + 礼一4 7 1 , 1 + n 2 + n 一4 = 2 n 一4 ， 因此 8 8 = 2 ，他= 燕，r + n 一2 = 雨2 n r 因此 川= 墨一n = 是2 仇r + 2r + 由此可得n = r + 2 ，即砌= r ，这与r 8 = 3 ，+ 掣一1 ：礼。， 故有3 r + ( r + 3 ) n i 一3 = 3 n x r ，即3 r + 3 n l 一3 = 2 n l r ，3 ( n l 一1 ) = r ( 2 n l 一3 ) 因 为r s = 3 ，所以 ( 口) 若n 1 ；，则3 ( n l 一1 ) 3 ( 2 n l 一3 ) ，由此可得3 仃l 6 ，即n l 2 ，而m 为整数， 得到矛盾 ( 6 ) 若扎1 ；，则3 l 一1 ) = r ( 2 n l 一3 ) 2 ，矛盾 通过上述讨论可知必要性得证 若g 兰倪或g 笺( 2 。一2 或g 皇k 4 ，图g 均满足( 1 ) 式，此时g + + 一是正则图，充分 性得证一 定理2 2 3 设图g 是仃( 22 ) 阶简单图，有m 条边，则g + 一+ 和g 一+ 一是正则图当且 仅当g 为侥、j 白、j g 、k s , s 或g o ，其中图g o 如下图所示 g o 图1 证明由于g 一+ 一= ( g 斗一+ ) 。，只要讨论图g + 一十的正则性即可 先证必要性：由表1 知，对g 中的任一顶点口，都有d g + 一+ ( ) = 2 d g ( t j ) ；而对任一条 边e = 罄铆昱( 固，都有如一+ ( ) = m + 3 一d c 一d g ) 若图g r + 一+ 是正则的，易 知g 也是正则的现不妨设g 是r 正则图，则m + 3 2 r = 2 r ，也就是钟+ 3 = 4 r ，即 r ( s m = 6 第二章：交换图的正则性华东师范大学硕士论文 1 1 因此n 8 且8 一f l i6 ，故8 7 1 = 1 、2 、3 或6 ，所以n 只能为2 、5 、6 或7 以下分情况讨 论 情况1 若n = 7 ，由( 2 ) 式知r = 6 ，即g 岂玛 情况2 若n = 6 ，由( 2 ) 式知r = 3 ，即图g 是3 - 正则的6 阶图易知3 征则的6 阶 图只能是娲3 或g 0 故g 型硒，3 或g 鲁g o 情况3 若n = 5 ，由( 2 ) 式知r = 2 ，即图g 是2 正则的5 阶图，那么只能是g 兰侥 情况4 若n = 2 ，由( 2 ) 式知r = 1 ，即图g 是1 正则的2 阶图，那么只能是g 笺k j 由此必要性得证 若g 为g 、玛、恐、。3 或g o ，由于它们都满足( 2 ) 式，故此时g + - + 是正则图充 分性得证一 定理2 2 4 设图g 是n 阶简单连通图，有m ( 1 ) 条边，贝t j g - + + 和6 叶一是正则的 当且仅当g 是咛_ 正则图 证明由于g 一+ + = ( g + - - ) 。，只要讨论图g + 一的正则性b l i , - 1 先证必要性由表1 知，对g 中的任一顶点 1 3 ，都有d 。+ 一( 口) = m ；而对任一条边e = l l , w e c a ) ，黼i d o + 一( e ) = m + n 一1 一d g 似) 一d 。( 伽) 因此若图( + 一是正则的，则 d a c u ) + d c ( w ) = 礼一1 ( 3 ) 对任意一条边e = 伽e c g ) 考b 成立又g 是连通的，与定理2 2 2 中的证明一样，可 知g 是正则图或半正则二部图以下分情况讨论 情况1 若g 是正则图不妨设它是r 一正则的，则由( 3 ) 式即知r = 2 手，即g 是堡一 正则图 情况2 若g 是半正则二部图不妨设y ( g ) = h u ，n v 2 = 0 ，( k ) ，( k ) 都 是空图，lu | - n l ，ikl - 他根据( 3 ) 式可知h 中的点在g 中的度都为他，而且k 中 的点在g 中的度都为7 , 1 1 ；或m 中的点在g 中的度都为n 2 1 ，而且中的点在g 中 的度都为n 1 对于前者必有”1 n 2 = m ( n 1 一1 ) ，对后者则有n l ( n 2 一1 ) = n 2 n x 由此可 得n l = o 或他= 0 这显然是不可能的故图g 不可能是半正则二部图由此必要性得 证 当g 是孚正则图时，易知( 3 ) 式得到满足，故图g + 一是正则的充分性得证 备注2 2 5 定理2 2 4 中正则性的充要条件要求n 必须是奇数，即g 必须是奇阶图 第三章变换图的谱性质 图谱理论是图论中的一个相当重要，也是非常活跃的一个研究方向，它的研究和发 展有着重要的理论和实际意义不仅促进了和丰富了图论与组合数学本身的研究，而且 在量子化学，物理，计算机科学，通信网络及信息科学中有着广泛的应用一系列的专 著【1 ，1 0 ，2 3 ，2 4 陆续涌现在图谱理论的研究中，谱半径的上下界及其估计一直是一个热 点问题现在已经具有了比较成熟的理论，技巧和方法在本章中我们依据前人有关图的 谱半径上界的结果和变换图的连通性得到八类变换图的谱半径上界及其估计 3 1 变换图的连通性 显然某些谱半径的界是以图的连通性为前提条件的如果要把这些界用于变换图，就 有必要探讨变换图的连通性事实上，早有学者对变换图的连通性进行了研究【6 】，并得到 了非常简洁的结果这些都是研究变换图谱性质的良好基础： 引理3 1 1 【6 】对于任意给定的图g ，则有 ( 1 ) 图g + + + 连通当且仅当g 连通 ( 2 ) 图g + + 一连通当且仅当g 至少有两条边且g 不是2 j b ( 3 ) 图g 一+ + 都是连通的 “) 图g - + 一连通当且仅当g 不是星图 ( 5 ) 图g + 一+ 连通当且仅当图g 不含有孤立点 ( 6 ) 图g + 一连通当且仅当图g 至少含有两条边 ( 7 ) 图g 一+ 都是连通的 ( 8 )图g 连通当且仅当g 既不是星图也不是j 岛 第三章：交换图的谱性质华东师范大学硕士论文1 3 3 2变换图的谱半径上界及其估计 接下来根据已有的一些图的谱半径上界及研究方法给出变换图的谱半径上界 引理3 2 1 3 1 】设g 是一简单连通图，有n 个顶点m 条边，a 是图g 的邻接矩阵则 p ( 舢川丽= ；再1 ， 且等号成立当且仅当g 星图或完全图 引理3 2 2 【2 1 】设n 阶图g 的顶点度序列为d l d 2 d ，i ，则 p ( a ) 定理3 2 3 设g 是祀( 3 ) 阶简单连通图，有m 条边，则 p ( g + + + ) , 、2 r n n + 3 m - n 2 + 1 证明由引理3 1 1 及题设条件可知图g 卅连通设图g + + + 有0 个顶点，仇，条边 对图g 抖+ 应用引理3 2 1 即得 p ( c + + + ) 4 2 m 一+ 1 = 2le ( g + + + ) l lv ( g + + + ) l + l 根据引理3 2 2 ，p ( g ) 、：。y ( g ) 略( ) ，即。y ( g ) 硌扣) 竹矿( g ) 由此可得 p ( g + + + ) | 、3 m - n + 1 + n p 2 ( g ) 对图g 再应用引理3 2 1 可得 p ( g + + + ) 钥磊磊了再习芴= 再可= 、2 r a n + 3 r a - n 2 + 1 要使p ( c + + + ) 达到该上界，上述不等号都必须成为等号，而这必须g 垡1 i m 一1 或g 掣 ，同时g + + + 望玛一一1 或g + + + 型k ，根据变换图的定义及图珞，硒加1 的特征易 知这是不可能的，故p ( g + + + ) 的该上界是不可达的 第三章：变换图的谱性质华东师范大学硕士论文 1 4 备注3 2 4 对于定理3 2 3 中的谱半径上界，容易估计得： 。( 、2 r n n + 3 m - n 2 + 1 ) 倒俪) 0 ( 、学) 由此可知定理3 2 3 中的上界为d ( 乎( m + n ) ) ，这远小于图g + + + 的点数m + n 与定理3 2 3 的证明方法一样，还可以得到： 定理3 2 5 设g 是礼( 2 ) 阶简单连通图，有m ( 2 ) 条边，且g 不是2 k 2 则 p ( g + + 一) 4 m n - n 2 - 5 m + 1 备注3 2 6 与备注3 2 4 的方法一样，有 4 m n - n 2 - 5 m + 1 ( m + n ) 2 - 2 n - 2 m + 1 = m + n 一1 即定理3 2 5 中的上界不超过f n , + n 一1 定理3 2 7 设g 是竹( 3 ) 阶简单连通图，有m 条边，则 p ( g 一+ + 、 2 m - f 2 n ， 因此 、，4 m n - 9 r n - n + l 4 m n - 2 m - 2 n + 1 x ( m + n ) 2 - 2 m - 2 n + 1 = m + n 一1 即定理3 2 9 中的上界严格小于m + n 一1 定理3 2 1 1 设g 是n ( 3 ) 阶简单图，有m 条边且g 中无孤立点，则 p ( g + 一+ ) c m 2 + 6 m - 2 n + 1 证明由引理3 1 1 及题设条件可知图g + 叶连通设图g + 一+ 有个顶点，m ，条边 第三章：变换图的谱性质华东师范大学硕士论文1 5 对图g + 一+ 应用引理3 2 1 即得 p ( g + - + ) 以万二了了了了 = 币琢f 可t = t 而萝= 干丌石 注意到g 中无孤立点，故对任一顶点t ，y ( g ) ，都有如( t i ) 1 ，因此 p ( c + 一+ ) s 石万丽万j 再t = i = m 2 + 6 m - - 2 n + 1 要使p ( c + 一+ ) 达到此上界，必需g + 一+ 岂k 一一l 或g 叶一+ 皇j o ，并且对任一顶 点口y ( g ) ，都有d g ( ) = 1 ，即图g 是1 棚子且图g + 一+ 是星图或完全图根据变换图 的定义及星图、完全图的特征，易知这是不可能的，故p ( g 咔- + ) 的该上界是不可达的_ 备注3 2 1 2 注意到n 3 ，容易得到： m 2 + 6 r a - 2 n + 1 、r a 2 + 6 m - 5 m + 3 即定理3 2 1 1 中的上界为o ( - 0 i 两样与定理3 2 1 1 的证明方法一样，我们还可以得到： 定理3 2 1 3 设g 是n 阶简单图，有m ( 2 ) 条边且g 中无孤立点，则 p ( a + 。1 m 2 + 2 r a n 一2 m 一2 n + 1 备注3 2 1 4 易知 、m 2 + 2 r a n - 2 m - 2 n + 1 4 m - - n ，于是，2 m 一3 n 2 m n 一2 m 一 2 竹，故 | 、m 2 + n 2 + 2 m - 3 n + 1 、m 2 + n 2 + 2 r a n - - 2 m - 2 n + 1 = m + n 一1 第三章：交换图的谱性质华东师范大学硕士论文 1 6 即定理3 2 1 5 中的上界严格小于m + n 1 定理3 2 1 7 设g 是礼阶简单图，有m 条边且g 中无孤立点，同时g 既不是玛，也 不是星图，则 备注3 2 1 8 易知 x m 2 + n 2 + 2 r a n - 6 m - 3 n + 1 p ( r h + ) 日 图5 比较图对+ + 和图日，易见图日添上边他，) ，i = l ，2 ，r j = l ，2 ，8 后即与 图对+ + 同构由此根据引理3 1 1 和引理4 2 2 可知p ( 对+ + ) p ( 日) 因此p ( 对+ + ) p ( t + + + 1 - 通过上述论述，可知由任一棵树至4 星的移接变形过程中，不仅树的谱半径不断严格递 增，相应的树的全图的谱半径也不断严格递增由此就可以得到下述定理： 定理4 2 4 设n 3 ，则对中的任一棵树t ，必有p ( 2 1 + + + ) p ( k 亡描) ，且等式成 立当且仅当t 笺塌。- 1 第四章：树的全图 华东师范大学硕士论文 2 1 4 3 星图的全图的谱半径 为了更精确地计算或估计星图的全图的谱半径p ( 瞄) ，这里先给出引理 目l l l 4 3 1 。= ( a 一卢) “一2 n a + ( n 一2 ) x , f l 一( 一一1 ) a b l ，喜e 中 是礼( 3 ) 阶行列式 n5 ao口口o b 旺；b8 _ b b 8 盘 9 8 b 卢p 卢a 证明先将。的第二行乘以一1 后分别加到第三，第四，第析，然后将第三，第 四，第n 列的元素都加到第二列，可得 = c 。一p ，“一2 i ：q + ( n 。- n 一1 ) a 。，p i = ( 口一国”2 协a + ( 礼一2 ) 郑一( n 一1 ) 口翻_ 引理4 3 2 【叫设n 阶( 0 ，1 ) 方阵b 的行和是n ，也，则 m i n r 1 ，r 2 ，) p ( b ) sm a x ? - 1 ，r 2 ， 接下来，我们就来计算星图的全图的谱半径容易知道，星图k 1 ，。- 及其全图如 图6 所示由此星全图的特征多项式p ( k 土描，a ) 为： o 笱 d 一 一o o o 0 + 一 入b o o q 第四章：树的全圈华东师范大学硕士论文2 2 j h m 一1 p ( 础，a ) = 图6 瑞 a 一1 1 一1 1 1 一1 1ao 0 10 0 - 10a 00 - 1 o 一1 0o a00 一1 1 10 0a 一1 一1 一l0 1 o 一1a 一1 一l 0o 一1 1 1 天 将上述行列式中的第n + 1 ，n + 2 ，2 n 一1 列的元素都加到第1 列上，就会得到 p ( 瞄，a ) = a + 礼一1 1 1 一l 一1 一l 一1 oa0 0 1o o 00a 00 1 o o 00 a0o 1 n 一3 一a 一1o 0a 一1 一1 n 一3 一a0 1 0 1a 一1 n 一3 一a00 一1 1 1 a 第四章：树的全图华东师范大学硕士论文2 3 再把上述行列式中第行+ 1 ，n + 2 ，2 n 一1 列的元素分别乘以a 并加到第2 ，3 ，n 列 上得到： p ( 磷，a ) = a + n 一1 一a 一1 一a 一1 一a 一1 1 1 一1 o00 o - 10 0 0 0000 - 1 0 000000 一1 n 一3 一a 妒一1- ) 1 一a入一1 一1 n 一3 一aa 芹一1 一a la 一1 ， n 一3 一a aa 舻一1 1 1 a 根据l a p l a c e 展开定理，取定上述最后一个行列式中第2 ，3 ，礼行，可将2 n 一1 阶行列 式降阶为竹一1 阶和n 阶行列式： j p t l 4 r - - 1 + m + 一+ l ，砷 =( 一1 ) 二m 槲竹+ 1 + 扣+ 2 ) + + ( 孙一1 ) 一1 0 o 然后根据引理4 3 1 即得到 0 - 1 0 o o 一1 a + 1 1 , 一1 - 1 一a - 1 一a - 1 一a n 一3 一aa 2 1一a 一a n 一3 一a a 舻一1 一入 n 一3 一a 一入一a 妒一1 p ( 瞄，a ) = ( 舻+ a 1 ) “一2 ( a 3 一( n 一2 ) x 2 一( 2 n 一1 ) a + ( n 一1 ) ( n 一4 ) ) 这就是瞄的特征多项式由于a ( 磷) 是实对称的，故其特征多项式的根皆为实数 易知a 2 + a 一1 = o 的正实根为掣显然根据引理4 3 2 ，p ( 磷) 6 = 2 而午 0 ，f ( - 一1 ) 0 因此必有n 一1 a l m 备注4 3 4 ( 1 ) 根据前述计算所得的k 王描的特征多项式，不妨设，( a ) 的另外二根分别为k 和 k ，且有沁之k 同时易求得方