（运筹学与控制论专业论文）两类图的谱半径和极图.pdf

摘要 近半个世纪以来，谱图论形成发展成为图论研究的重要领域之一，也是 一个非常活跃的研究方向，它在量子化、物理、计算机科学、通信网络 及信息科学申均有广泛的应用图谱理论的研究主要是利用成熟的代数理 论和技巧，并结合图的拓扑结构性质和组合数学的理论、矩阵理论采研究 图谱及其与图的结构性质、图的其它不变量( 如色数，度序列，直径，连通度 等) 之间的关系，将图与网络的代数j | 生质与图的拓扑性质紧密地联系在起 本文中分两个部分集中反映了作者三年来围绕般简单连通无向图的 邻接谱的界所取得的主要结果，包括两类特殊图类的邻接谱，具体结果如下： 1 研究特殊图类树t 的谱半径，得出n 阶树的n o r d h a u s - g a d d u m 类 型谱半径的可达上界： p ( t ) + 户( t 。) 、而+ 礼一2 ， 等号成立当且仅当t 竺髓，l ，其中t 。为t 的补图，硒，1 为扎阶星图 2 研究了直径为3 的树的n o r d h a u s - g a d d u m 类型谱半径，并证明了 对于“阶双星图s 扛，6 ) 的n o r d h a u g a d d u m 类型谱半径随。的值单调上 升，其中 与旦】n n 一3 3 利用移按变形的方法研究具有七条割边的图的谱半径的上界，给出 了该图类谱半径达到最大和第二大的极图 关键词：树，补图，割边，移接变形，谱半径 a b s t r a c t t l es p c c t r a lt h e o r yo fg r a p h1 8n o to n l ya ni m p o r t 舶1 ta r e ai ng r a p ht h e - o r yb u ta 1 8 08 na c t i v et o p i c t h e r ea r ee x t e n s i v ea p p l i c a t i o n si nt h ef l e l d 8o f q u a n t u mc h e m i s t r y ，p 1 1 y s i c s ，c o m p u t e rs c i e n c e ，c o m m l m i c a t i o nn e t 、m r ka n d i n f o r m a t i o ns c i e n c e t h et h e o r y0 fg r a p h sa dr e l a t i o i l sb e t w e e nt h cs p e c t r a a n d 敛e dv f h i a t e ( e g c h r o m a t i cn u m b e r ld e g r e es e q u e n c e ，d i a m e t e ra d c o n n e c t i v i t y ) o fg r a p h sb ym e a n so ft h ew e l l d e v e l o p e dt h e o r ya n dt e c h n i q u e o fa l g e b t a ，七o p o l o g l c 如s t r u 毗u t ep r o p e t 髓e sd g r a p h ，c o m b i n 眺i o na n dm a - t r i xt h e o r i e ss o a st oe 8 t a b h s h 丘r me s s e n t i 出r e l a t i o nb e t r e e nt h ea l g e b r a i c p r o p e r t i e sa n dt o p o l o 百c a lp r o p e r t i e so fg r 印h sa n dn e t w o r l 【s i nt h i sp 印e r ，w em a i n l ys t u d yt h ea d j a c e n c ys p e c t r l l l l lo f8 i m p l ec o n n e c t e du n d i r e c t e dg r 印h s s o m er e s u l t sw i l lb eg i 、，e ni nt h i 8t h e 8 i s 1 b yu s i n gt h ei m p r a v e dm e t h o do fg r a rt r a n s f o r m a t i o n ，t h e8 h a r p u p p e rb o u n do nt h es p e c t r a lr 甜i u 8t h en o r d h a u 争g a d d u mt y p ea tt r e e si s g i v e n w es h a wt h a t p ( ? ) + p ( t 。) 、石习+ 礼一2 t h ee q u a l i t yh o l d si fa n do n l yi ft 皇研舻1 2 w e s t u d yt h et r e ew i t hd i 啪e t e r3 w ep r a v et h a tt h es p e c t r mm d i u s o ft h en o r d h a u s - g a d d u mt y p ef 【) rd o u b l e _ s t a rs ( o ，6 ) i ss t r i c t l yi n c r e a 8 i n gi n v a r i a b l e 口，w h e r e 鼍量 sn n 一3 3 w es t u d yt h es p e c t r a lr a d i u so fg r 印h sw i t hkc u te d g e s ，a n dt h e s h a r pu p p e rb o u n do nt h es p c c t r a lr a d i u s0 fg r 印h sw i t hk c u te d g e si 8 百v e n b va n o t h e rm e t l l o d w es h o wt h et y p e so fg r 印h sw i t ht h el 叫筘8 ts p e c 七r m r a d i u s 蛆dt h eb e c o n dl 缸g e s t 印e c t r 以r a d i u sa m o n ga ut h eg r a p h sw i t hk c u te d g e sr c 8 p e c t l v e l h k e yw o r d s ： t r e e ，c o m p l e m e n tg r a p h ，g r a f tt r a n s f o r m a t i o n ，c u te d g e ，8 p e c t r h 】r a d i l l 8 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的 研究成果。据我所知，除文中已经注明引用的内容外，本论文不包含其他 个人已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和 集体，均己在文中作了明确说明并表示谢意。 作者签名：伺秒日期：孤上刁 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有 权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质 版。有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书 馆被查阅。有权将学位论文的内容编入有关数据库进行检索。有权将学位 沦丈的标题和摘要汇编出版。保密的学位论文在解密后适用本规定。 学位论文作者签名：硒秒 日期：。”b - 习 导师签名： 日期： 彬 0 第一章概述 图论是一门应用广泛的数学分支，是处理离散数学问题的强有力的工 具图论同时也是运筹学，电路网络，计算机理论研究类和实践应用中不可 缺少的数学工具不仅如此，它在开关理论，编码理论，计算机辅助设计，甚 至于社会科学，化学，物理等领域都有广泛的应用，因此无论就图论的理论 价佤还是其实际应用的广度和深度来看，图论及其应用的研究正处于一个 具有强大生命力的蓬勃发展的新时期图论的研究内容及其独特的研究方 法，随着现代科技的不断飞速发展越来越显示出其独特的作用和魅力 图谱理论是图论研究的重要领域之一图谱在量子化学，统计力学， 通信网络及信息科学中均有一系列的重要应用自从本世纪五十年代 lc o l l a t z ，u s i n 0 9 0 w i t z ( ( 5 】1 9 5 7 年) 被认为开创性文章发表以来，随着对 图谱理论的研究不断发展和深入，这方面的大量研究成果相继发表在国内 外的许多重要学术刊物和专著中( 【1 】， 4 1 ，【7 】，【8 】，【9 】，【1 7 】，f 2 1 】， 2 2 】，【2 6 ) 一系列关于图论的专著( 1 ， 6 ， 9 】， 1 l 】) 不断丰富和促进着这门学科的发 展，其竞早在1 9 3 1 年，e h i c k e l 等理论化学家们就对图的谱理论产生了浓 厚的兴趣，并着手进行研究尽管他们所采取的符号和术语与现代科学家 所用的不一致，但是却大大推动了图谱理论的研究正因为诸多著名的组 合，图论扣代数方面的科学家( 如a j h o 伍m a n ，c d g o d 8 i l ，r a b r u a l d i r p s t a l e y ll l 0 v d 8 z ，n a s h _ w i l l i a m s ) 以及理论化学家，物理学家( 如a t ， b 甜a b a n ，a s t r e i t w i e s e r ，r m e r r i s 和i g u t m a n ) 都在这一领域做了许多深 入的研究工作，使得图谱理论在近半个世界得到飞速发展，尤其在近二十年 来它已经成为图论中一个非常活跃的研究方向 研究图谱理论的意义在于它促进和丰富了图论和组合学本身的研 究，谱技巧已成为图论和组合学研究中一个重要的工具著名组合学家 n a s h w i l l i a m s 在论及图谱时讲道：“有些其特征上是纯组合的主要结果有 这样奇妙的特性，即如果不借助涉及图的邻接矩阵的特征根的代数方法，是 不可能得到现在所知的结论的” 经过数十年的研究，人们对图谱理论的认识已经相当广泛和深入图谱 理论所研究的对象主要包括图的邻接谱，l 印l a c i a n 谱，q 一谱，c - 谱，s 谱，其 中对邻接谱，l a p l a c i a n 谱的研究最为普遍图谱理论呈现出丰富多彩的形 式，而且各种不同定义的谱之间有着相互联系 1 1基本概念 本文所研究的图均为无环、无重边，有限无向的简单连通图所有的专 业术语均可参考文献2 1 设图g = ( k e ) ，其中y 为顶点集，y = y ( g ) = u 1 ， 2 ， 。) ， i y l = n 称为图g 的阶数，e 为边集，e = e ( g ) = e l ，e 2 ，e 。) ，i f l = m 为图g 的边数若e 的两个端点分别为顶点让与u ，记为e = ( “， ) = u u ， 则称顶点u 与u 相邻接，记为“一u ；否则称它们不相邻，记为“口若 边e = ( “，u ) e ，则称u 或者u 与e 关联与 关联的边的个数称为u 的度，记作d e g ( ) = 也图g 中最大、最小的顶点的度分别记为( g ) 和d ( g ) ，图g 的度序列就是由g 的各顶点的度为元素的序列，通常按不 增的顺序写作( d 1 ，d 2 ，如) ，其中d l d 2 如0 ( ) 表示顶点 在图g 中的所有邻点所组成的集合对于连通图g ，定义两个顶点饥 之间的距离为中最短“一 路的长度，简记为d ( ，u ) 顶点“的离心率 2 e ( u ) ：m 口。v ( g ) d ( u ，u ) ，图的直径d = d d m ( g ) = m 口z u v ( g ) 8 ( u ) 由直径 的定叉可知d = m o z 。舴v ( g ) d 沁w ) 图g 的邻接矩阵记为a = a ( g ) = ( ) 。是一个n 阶的( o ，1 ) 一方 阵，其定义如下： 旷 ：篡 显然，d 。= o ，8 妇= q ，故而a ( g ) 是一个实对称方阵我们称d e t ( j a ) 为图g 的特征多项式，记为p ( g ) 或p ( g ；a ) 它的特征值a l ，a 2 ，k 均 为实数，不妨将其由大到小排列为a 1 2 k 根据a ( g ) 的定义， 我们有九= o ，碍= 2 m 这些特征不以顶点标号顺序的不同而改变， 我彳f j 记a ；( g ) = a ，( a ) = l0 = 1 ，n ) ，称 s p e c g = a l ( g ) ，a 2 ( g ) ，a 。( g ) 为图g 的邻接谱，或记为 鼬一k ，意：， k m ( 沁) 这里 1 ) 、2 九，m ( 凡) 为k 的重数显然 完全图甄的邻接谱可表示为 沁= l ，) 最大特征值a 1 ( g ) 也称为图g 的邻接谱半径，在不致混淆的情况下， 简称为图g 的谱半径，通常记为p ( g ) 或p 当图g 连通时，a ( g ) 是一个 非负不可约矩阵，根据矩阵论的知识( p e r r o n - n o b e n i u s 定理) 【19 ，p ( g ) 为 如洲n = 协 m ，嘲 单根，并存在一个单位正特征向量$ 一( 。- ，z 2 ，。) 7 与p ( g ) 相对应，即 孔 o ，a ( g ) 。= p ( g ) 。，其中对应于顶点吡0 = 1 ，n ) 祢。为a ( g ) 的p e r r o n 向量，简称g 的p e r r o n 向量 p e r r o n n o b e n i u s 定理( 【1o 】【2 5 】( 【17 】p 3 2 ) )设b 是n 1 ) 阶不 可约非负方阵，记p ( b ) = m n z l a ，f ，l a 2 i ，l a 。i ) ，这里 a l ，a 2 ，k ) 是 b 的扎个特征值，则 ( 1 ) p ( b ) 是b 的特征值； ( 2 ) p ( 口) 作为b 的n 2 个元素的函数是严格递增的，即若有b g ，g b o ，则p ( a ) p ( b ) ； ( 3 ) p ( 口) 是b 的单根； ( 4 ) b 有正特征向量z 与p ( b ) 相应，即b ：= p ( b ) z 而且b 的任一 j # 负特征向量一定是z 的正整数倍 如果两个具有相同顶点集y 的图g 和h 满足 e ( g ) 当且仅当 u 雁e ( 日) ，也称图g 和图打是互补的，则称图日为图g 的补图，记为 h = g c 记树t 的谱半径为p ( t ) ，树t 的补图为p 图及其补图的谱半 径之和称为图的n o r d h a u 8 - g a d d m 类型谱半径，即为p ( g ) + p ( g 。) 在图g 中，如果图的两个顶点牡和口之间存在一条u 一 路，则称两个 顶点u 和是连通的如果g 中任何两个顶点都是连通的，则称图g 是连 通的或称g 为连通图，否则就称g 是不连通的或g 为不连通图“连通” 关系是图g 顶点集上的等价关系，由每个等价类导出的子图称为g 的连通 分支或简称为g 的分支图g 的一个分支是g 的一个连通子图，且不会作 为g 的其它连通子图的真子图，即g 的一个分支对连通性来说是一个最大 的子图图g 的不同连通分支个数称为g 的分支数，用女( g ) 表示如果图 4 g 的顶点 y ( g ) 满足( g 一。) ( g ) ，那么顶点u 称为图g 的割点 如果图g 的边e e ( g ) 满足( g e ) ( g ) ，那么边e 称为图g 的割边， 设g 咄= g ig 为n 阶简单图，具有条割边) 同时，对图 g = ( v e ) ，。，口v ( g ) ，z e ( g ) ，用符号g z 表示图g 去掉点u 后 的子图，用g z 表示图g 去掉边。后的子圈类似的，若z ge ( g ) ， 用g + z 表示图g 增加边z 后的子图 给定图g = ( v e ) ，若y 7 y ，e = u e k u y ) ，则称图 g 7 = ( y ，e ) 是g 中由y 生成的子图，记g 为g 【y 】 设图g 为任意图且g 代表颜色集合，如果存在映射口：y ( g ) 一e 使 得对任意“ e ( g ) ，口( u ) 口( u ) ，则称口为g 的顶点染色或者染色法，即 对g 的每个顶点用g 中的莱种颜色使得每个顶点只染一种颜色，且相邻两 个顶点染不同的颜色如果在图g 的某种染色法中总共使用的颜色不超过 p 种，则称它是图g 的p 一染色法，且称图g 是p 一可染色的。如果存在图 g 的g 一染色法，那么对任意p 口，g 存在p 一豪色法显然，如果g 是n 阶图，则g 是札一可染色的对图g 的顶点染色需要的最少颜色数称为g 的点色数，或简称为g 的色数，并用k ( g ) 表示，筒记为k ， 此外，还有些未给出的专业术语与记号将分别在文中的相关章节里给 出或参阅吲， 2 】在不致引起混淆的情况下，上面的记号可将g 省略，如 a 、p 等 5 t 1 2本文主要内容 本文重点研究了两类特殊图类的谱半径的上界及其极图，主要结论如 第二章主要围绕n 阶树的n o r d h 一g a d d u m 类型谱半径展开在第 一节中，我们综述了一般图类的n o r d h a u s g a d d u m 类型谱半径的已有的研 究结果，同时描述了平面图该类型谱半径上界的改进历程，对于此类问题作 了较全面的综述 在第二节中，我们利用矩阵论理论，得到n 阶树t 的n o r d h a u s g a d d m 类型谱半径的可达上界，即： 定理2 21设t 为n 阶树，则 p ( t ) + p ( r ) 、而+ n 一2 ， 等式成立当且仅当丁型k 1 。- l 在第三节中，我们研究了直径为3 的n 阶树即双星图s ( o ，b ) ( 口b 1 ) 的n o r d h a u 8 g a d d u m 类型谱半径，得出该类树的n o r d h a u 8 一g a d d u m 类型 谱半径随n 的值单调上升，其中 咛1 墨。sn 一3 ， 在第三章中，我们利用移接变形的办法研究了具有条割边的图的邻 接谱半径，分别刻画出其邻接谱半径达到最大乖第二大时的极图 在第一节中，我们对目前已有的具有个割点的图的邻接谱半径的界 和具有条割边的图的邻接谱半径的界等研究情况进行了综述 在第二节中，我们研究了具有条割边的图的邻接谱半径，用另一种方 法推导出该邻接谱半径达到最大的极图： 6 定理3 2 1 设g 为具有条剖边的n 阶简单图，即g g 毗则 p ( g ) sp ( g o ) ， 等式成立当且仅当g 型g o ( 具体见图3 2 ，1 ) 在第三节中，我们仍研究具有务割边的图的邻接谱半径，刻画出在一 定条件下该谱半径达到第二大的极图具体结论为： 定理33 1 对任意g g 咄，且g 掌岛，当学时，则 p ( g ) p ( g 1 ) 等式成立当且仅当g 竺g l ( 具体见图3 3 1 ) 7 第二章 树的n o r d h a u s g a d d u m 类型谱半径 图及其补图的谱半径之和称为图的n o r d h a u s g 甜d u m 类型谱半径本 章给出了n 阶树的n o r d h a u 8 g a d d u m 类型谱半径的可达上界： p ( r ) + p ( t 。) 、厅f 二了+ n 一2 ， 等号成立当且仅当t 兰k l ，1 ，其中丁。为t 的补图，k 1 一l 为n 阶星图 同时，本章还证明了对于n 阶双星图s ( 口1 6 ) 的n o r d h a u 8 - g a d d u m 类型谱 半径随。的值单调上升，其中【宁 口n 一3 2 1引言 本章我们主要研究特殊图类树的n o r d h a u 8 g a d d u m 类型谱半径，在此 之前，我们首先对般图类的n o r d h a u s - g a d d u m 类型谱半径的研究成果作 一综述 1 9 5 6 年，e a n 。r d h a u s 和j w g a d d u m 2 4 】最早考虑了图及其补图的色 数之间关系扎阶图g 和其补图g 。的色数分别记为k 和丙，他们证明了下 列关系： 2 元尤+ 霄n + 1 ， 七葡sn 这些关系式为以后的色数研究带来了很大的方便所以此后的文献中将图 与补图的某一参数之和或积称为n o r d h a u 8 - g a d d u m 图类的参数 早在1 9 7 0 年，e n 0 s a l f 2 3 在其硕士论文中就给出了n 。r d h a u s g a d d u m 图类的谱半径的一个十分简易和优美的上界和一个可迭下界： r 对任一n 阶简单图g ，则 n 一1 p ( g ) 十p ( g 。) s 、互( n 一1 ) 右边等式成立当且仅当g 为正则图， 因而以g ) + 反g c ) 下界n 一1 为可这的，而p ( g ) + p ( g 。) 上界 ( n 一1 ) 却是可被进一步改进 近几年来，国内有关p ( g ) + p ( g c ) 上界的改进的结论不断出现 1 9 9 3 年，徐寅峰 3 2 1 得到 n 阶简单图g 则 p ( g ) + p ( g 。) s 一1 + 、互元f 二i 而 一1 + 、丽， 料嗣 掣十； 1 9 9 6 年，李秀兰f 1 6 】给出了p ( g ) + p ( g c ) 的另一上界： p ( g ) + p ( g 。) 1 + 、可了i 鬲百_ = i _ 二i 面i = 1 同， 其中和6 分别为图g 的最大，最小度 若图g 和g c 均连通，则 p ( g ) + p ( g 。) s 撕万j 而 1 9 9 7 年，周渡【3 4 】也对简单图，连通图及连通平面图分别给出以下结论： 对任一佗( n 2 ) 阶简单图g ，有 邸) + p ( g c ) 一；+ 。丽， 僻删 学一1 掣+ 杀 若g 与g 。都连通，则 p ( g ) + p ( g 。) 以百j _ 两， p ( g ) p ( g c ) 坠掣 若g 是连通平面图，则 粥) 州g c ) 、( n _ 1 ) ( n _ 2 ) + ：+ 丽+ ；， 一( g ) ，( g c ) 缸i 而j 而百习西两 + 4 、( n _ 1 ) ( n _ 2 ) + j 一；网十2 上面的结论均不是可迭上界，在2 0 0 0 年，洪渊和束金龙【2 8 利用图谱半 径的新结果，结合谱半径与色数之间的关系，得到图与其补图谱半径之和 p ( g ) + p ( g 。) 的三个上界： 若n 阶简单图g 有m 条边，色数为k ，则： 粥( g c ) 厄虿而 对任一扎阶简单图g ，有 邸) + 邸。) ( 2 一；) 咖一1 ) 其中t = m 溉 k ，而) 对任一n 阶简单图g ，有 粥) + 粥。) 、2 一当( n 一1 ) t 其中? = m n z k ，丙， 同时，他们还进一步得到p ( g ) + p ( g 。) 的可达上界 1 5 ： 若g 为n 阶图，则 p ( g ) + p ( g 。) 、( 2 一：一；) n ( n 一1 ) ， 等式成立当且仅当g 为完全图或空图 该结论不仅具有完美的对称性，而且是利用色数来反映p ( g ) + p ( 口) 的可达上界，同时， c = 、。一：一； 均小于2 2 0 0 4 年，施劲松 2 7 】又得出p ( g ) + p ( g 。) 上界与色数k 的另一关系： n 阶简单图g ，m 条边，色数k ，则 们) + 邸。) 以再一1 ) 一( 警+ 零) ， 其中丽= n m 一1 ) 一m 为g 。的边数，瓦为g 。的色数等式成立当且仅 当g 是完全图或或空图 注：若g 与g c 满足m 而，k 霄，有 邸m t g 何i 爵厄鬲 若g 为色数为k 的礼阶简单图，丁= m o z k ，耐，有 p ( g ) + 粥。) ( 2 一；) 咖一1 ) 若g 与g 。都连通，则 p ( g ) + p ( g c ) 、偶再面i 两i 在本章中，我们研究特殊图类树t 的p ( t ) + p ( p ) ，得到一个可达上界 定理2 2 1 设t 为n 阶树，则 p ( 丁) + p ( t 。) 、而+ 竹一2 等式成立当且仅当t 掣k 1 一1 另外，我们考察直径d = 3 的树t 即双星图s ( ，6 ) ( n 6 1 ) 的 n o r d h a u s - g a d d u m 类型谱半径，得到结论： 定理2 3 1 n 阶双星图s ( 8 ，6 ) 的谱半径随n 的值单调上升，即 删孚】，f 孚 ) ) 删孚字 榔刮) 其中n 6 1 ，口+ 6 + 2 = n ，【与量】茎o 竹一3 2 2树的n o r d h a u s - g a d d u m 类型谱半径的可达上界 引理 关于图的谱半径与其它参数的关系已有许多结果这里首先引用几个 由非负矩阵理论 2 2 有以下结论： 引理22 1 设a 是n n 阶非负不可约矩阵，谱半径为p ( a ) ，行和分 别为s l ，岛，s n ，则 惑s l p ( a ) s 燃& 其中任一个等式成立当且仅当a 的各行和均相等 对于一个简单连通图，有如下很简洁的结论 推论2 2 2 设g 为n 阶简单连通图，则 占户( g ) s ， 其中任一个等式成立当且仅当g 是正则图 引理2 2 3 若连通图g 为图9 的子图，则p ( g ) p ( 口) 关于树t 的谱半径p ( t ) 的上界，已有结果： 引理2 2 4 设t 为n 阶树，则 p ( r ) 、百1 ， 等式成立当且仅当t 兰髓。一1 由此得到本节的主要结论： 定理2 2 1 设丁为n 阶树则 p ( t ) + p ( r ) s 、，而+ n 一2 ， 】3 等式成立当且仪当l 型k 1 p l 证明：显然6 ( t ) = 1 ，它的补图t 。的顶点的最大度满足( t 。) 2 ( n 一1 ) 一d ( t ) = n 一2 若t 掌k l ，l ，则t c 一定是连通固由推论2 2 2 知p 。) 口。) 曼 n 一2 等式成立当且仅当t c 是( 扎一2 ) 一正则图显然t 不可能为 ( n 一2 】正则图于是p ( p ) 1 ，d e g ( ) 2 ，d e g 扣) 2 且七一f m ，l 1 随后，有很多学者对移接变形进行了深入的研究，得到了许多新的结果 ( 见【2 9 kf 3 1 】，【3 3 】) ，丰富和扩充了原来的李冯移接变形2 0 0 3 年吴宝丰在他 的硕士论文 3 0 】中给出了另外一种形式的移接变形，更加便于图的邻接谱的 1 5 b 、，llrj 研究 引理2 3 2 3 0 】设“，口是连通图g 的任意两个顶点，s ( 1 s d 。( w ) ) 为某一正整数若 u - ， 。，) 舀( ) k ( u ) 非空且z = 。l ，z 2 ，z 。) 是g 的p e r r o n 向量，其中鼢对应于顶点地( 1 i n ) 将g 中的边u 仇替换为“饥( 1 z s ) 得到图口若z 。，则 p ( g ) p ( 口) “g 图2 0 2 下面我们利用移接变形的方法考察直径d = 3 的树s ( 口，6 ) ( n 6 1 ) 的n o r d h a u s g a d d u m 类型谱半径 定理2 3 1 n 阶双星图s ( o ，6 ) 的谱半径随。的值单调上升，即： 删孚】， 字】) ) 俐字 + l f 字 榔刮) 其中o 6 1 ，n + 6 + 2 = 礼， 与量】口sn 一3 证明：设y ( s ，6 ) ) = “，口，u 1 ，“2 ，一，u 。， 1 ，吨，一，) ，其中( u ) = 削，扎l ，“2 ，u 。) ，( 训) = 让，”1 ，u 2 ， ( 见图23 1 ) 令。= ( z 。，霉。，。， z 。，茁。，z 2 ，。b ) t 为s ( n ，6 ) 的p e r m n 向量，其中茁。，。分别 对应顶点， ，z 。对应顶点“( 1 t 兰o ) ，而。对应顶点仇( 1 i 下面比较顶点u ，u 相应的p e r r o n 分量z 。和如的大小设p ( n ，6 ) ) = 1 6 p 由a ( s ( n ，6 ) ) 。= p 。，有下面关系式 触= + 肛。= 。邯+ z 。 l 茎j 茎6 z 。：三口。，z 。：三z 。，( 其中ls is 。，1 j 6 ) 。，2 2 ( 暑甲1s23o 1 3 。 由关系式( 1 ) 扣( 2 ) 可解得 ( 1 ) ( 2 ) ( 3 ) 由( 3 ) 可见n ，6 影响p 的大小因此由。+ 6 = 佗一2 ，令，( o ) = 一1 ) 2 4 0 6 = ( n 一1 ) 2 4 0 ( n 一2 一n ) ，则，7 ( 口) = 8 。+ 8 4 礼，故当o 2 笋时，( o ) o ， 即当o21 增加时p 值增大、即： 删孚m 字1 ) ) 删孚1 扎【孚 撕剖) 因而有双星图s ( ，6 ) 的谱半径随的值单调增加 口 本章主要的结论在于给出了：对于双星图的补图s ( 口，驴的谱半径也有 类似定理2 3 1 的结果 定理2 3 2 双星图的补图s ( 口加) c 的谱半径随口的值单调上升，即： 删孚1 ，【孚】) c ) p ( s ( 【孚1 + l ，【字】瑚 p ( s ( 口，6 ) 。) 类似可证得： 删字 ， 字 ) c ) 删孚】+ 1 ，【孚w ) 榔刮c ) 口 因此双星图的补图s ( 口，6 ) 。的谱半径随。的值单调上升 结合定理2 3 1 和定理2 3 2 ，得到下面的定理： 定理2 3 3 双星图s ( o ，6 ) 的n o r d h a u s g 甜d u m 类型谱半径随的值 单调上升，即 删孚】，【字) ) ) + p ( 剐孚】，【字】) c ) 】9 删孚，【字 1 ) ) + p ( s ( 【孚 + 1 字】删 - p ( s ( 礼一3 ，1 ) ) + p ( s ( 礼一3 ，1 ) 。) ， 其中o 6 1 ，口+ 6 + 2 = n ， 专】n sn 一3 从以上直径d = 2 ，d = 3 的树的补图的谱半径的结论看，p ( t ) 与p ( t 。) 似乎有相同的大小顺序，但是不然例如对于直径d = 4 的树t 就可以找 到反例 例当d = 4 ，n = 7 ，树丑和乃如下图( 见图2 3 3 ) ，有：p ( 丑) = 2 1 0 1 0 p ( 巧) = 4 5 1 1 4 第三章具有七条割边的图的谱半径的可达上界及极图 3 1 引言 2 0 0 1 年，a b r a h mb e r m a n 和张晓东3 1 通过讨论图的邻接矩阵的p e r r o n 向量，得到具有个割点的图的谱半径的界2 0 0 4 年，刘慧清，陆玫和田 丰 2 0 】得到具有条割边的图的谱半径的界，并得到达到最大谱半径的极 图本章主要通过移接变形的方法研究具有条割边的图的谱半径，给出了 该图类谱半径达到最大和第二大的极图 设 e 1 ，e 2 ，e ) 为图g 的割边的集合，则e t 有两种可能：为g 的 悬挂边或者非悬挂边不妨设g 中的非悬挂割边的个数为眠则g 悬 挂割边的个数为七一7 因而，图g d l ，e 2 ，) 为若干个互不连通 的2 一边连通分图和孤立点的并假定这些2 一边连通分图个数为f ，则孤立 点的个数为女+ 1 一z 设这些连通分图分别为目，岛，其顶点数为 n l ，n 2 ，m ，则g 一 e l ，e 2 ，e k ) = u 岛u u 呙u ( 南+ 1 一f ) k 1 ，有 忭1 + n 2 + + 啦+ ( 七+ 1 一f ) = 扎 为了方便起见，用符号g 1 ”g 2 表示由g 1 和g 2 组合所得到的图，其 中g 1 和g 2 有且仅有公共顶点 ，即g 1 g 2 的预点集为y ( g 1 ) uy ( g 2 ) ， y ( g 1 ) nv ( g 2 ) = ) ，且e ( g 1 g 2 ) = e ( g 1 ) ue ( g 2 ) ，可将g 1 g 2 看作由 g 1 和g 2 在公共顶点u 处粘连而戍 若g l 的顶点数为n l + 1 ，g 2 的顶点数为n 2 + 1 ，则g l u g 2 的顶点 数为n l + n 2 + 1 当g 2 为孤立点u 时，则g l g 2 = y ( g 1 ) 同理，周 g l u g 2 u g ；表示由g l 、g 2 、g f 在唯一的公共顶点 处粘连而成 2 1 的图、其中 的顶点数为m + 1 ，i = l ，2 ，2 此时，g 1 u g 2 ug l 的点 数为n 1 + n 2 十+ m + 1 = n 设g 矾= g 1g 为n 阶简单臣具有自条割边) 同时，对图 g = ( k e ) ，z ，口y ( g ) ，。口e ( g ) ，g 一。表示图g 去掉点得到的圈， 用g z 表示图g 去掉边得到的图类似的，若。掣e ( g ) ，用g + z f 表示图g 增加边z 得到的图，有以下熟知的结论： 命题3 1 1g = ( v e ) 为连通图，z fge ( g ) ，。，f y ( g ) ，则p ( g ) p ( g + z 掣) 3 2 具有南条割边的图的谱半径达到最大的极图 设为图g 的p e r r o n 向量，由a x = p 。，肛* = 巧容易得到下 列引理： 引理32 1 谈z = ( 盘1 ，$ 2 ，z 。) 为连通图g 的p e r r o n 分量，其中 孔分别对应顶点叫( 1 n ) ，若m ) = ( ) ，则毛= 吻 先给出该类图的特征： 图( 如图3 ，2 1 ) 是f 个2 - 边连通图，s 2 ，s ；在同一点彬处粘连， 同时训与k 个孤立点 1 ，吨，相邻所得到的图s 1 ，岛，s 的点数分 别为n 1 + 1 ，扎2 + 1 ，- ，n f + 1 ，g 的点数为n ，满足竹l 十佗2 + + n f + 缸 1 = 礼 圈日( 如图3 2 。1 ) 是1 个完全图j 。+ h 蚝。+ l ，。+ l 在同一点 出粘连，同时与女个孤立点吼， 2 ，相邻所得的图，其中礼l + 他+ - + 礼+ 膏+ 1 = n 图g o ( 如图3 2 1 ) 是一k 的一点 同时与盘个悬挂点相毒p 所得到的 n 阶简单 h g c 圈3 2 1 刘慧清，陆玫扣田丰在【2 0 】中已经给出了以下结论，本文中将给出另一 种证明 定理3 2 1 设g 为n 阶简单图，具有条割边，即g g 。则 p ( g ) p ( g 0 ) ， 2 3 等式成立当且仅当g 皇g o 证明： 论断一：设礼阶连通图g 具有条割边，则p ( g ) p ( 口) ，等式成立 当且仅当g 垒g + 设 e l ，e 2 ，雠) 为图g 的割边集合，g 一 e 1 ，e 2 ，钆) = 蜀u 岛u u s u ( + 1 一f ) k l ，根据图g 的这条割边的邻接点是否为悬挂点来 考虑它们的邻接点的移接变形情况不妨设g 中非悬挂的割边的个数为， 则g 中为悬挂边的割边有女一条 假设g 等口，讨论图g 中的女条非悬挂边的割边 首先，就g 中非悬挂边e 的两端的邻接情况分别进行计论令z = ( 。1 ，z 2 ，。) 7 为g 的p e r r o n 向量，其中奶对应于顶点让( 1s n ) ( 1 ) 设非悬挂边的割边e = “ 两端分别邻接图g 中2 边连通分图 & 和& 比较割边e 的两个端点u 和 的相应的p e r r o n 分量。和z 。， 不妨设。显然， 在s j 中的邻点集合a ( 口) 一 u ) 饥不妨设 g ( u ) 一 u 卜 口1 ，u 2 ，) c g ( ”) g ( u ) 非空，则将g 中的边口轨替 换为u 地( 1 i s ) ( 如图3 2 、2 ) 为了方便起见，称第一次移接受形后得到 图称为g 7 l ，此时& 和岛的公共顶点乱记为“1 ( 2 ) 设非悬挂边的割边e = 伽两端有顶点和其他悬挂边相邻，即e = 仳 或者邻接图g 中的一个2 一边连通分图& 和若干条悬挂边，或者邻接图g 中的其他两组悬挂边此时，通过比较顶点“和口对应的p e r r o n 向量分量 的大小，同样可以进行( 1 ) 的移接变形过程( 如图3 2 3 ) 专激 图3 2 3 显然g 1 仍然有条割边，其悬挂点比g 增加了一个点 ，即 g 7 l 比g 多了一条悬挂边，并且，岛，岛仍然为2 一边连通分图此 时，g l 一 e 1 ，e 2 ，e ) = u ：1 。戴，s mu u l 岛) 根据引理2 3 2 有 p ( g ) p ( g 7 1 ) 重复此过程，依次再对g ，1 中的7 1 条非悬挂边的两个端 点对应的p e r r o n 分量进行比较大小后进行类似的移接变形每一次得到的 新图g ；( 1si ”) 的割边数均不变，悬挂边增加一条，岛，岛，昌的 边连通性也保持不变，而谱半径却逐渐增九对g 的条非悬挂边的割边 进行移接变形后得到的图g ，仍为具有条割边的连通图此时，这条 割边均为悬挂边，且第i 次变形后的图均记为g ，对应的p e r r o n 分量大的 顶点移接变形后均记为啦，i = 1 ，2 ，