（基础数学专业论文）图的度序列和谱半径的界.pdf

图的度序列和谱半径的界 摘要 图的特征值的集合称为图的谱，其中最大特征值称为图的谱半径对 大量的图由于不能直接给出它们的谱，于是对图的特征值的估计就成为 了图谱中相对活跃的课题目前对该问题，特别是对谱半径的界的研究 已取得了不少成果，但对于其下界所得到的研究成果还较少本文主要 利用与度有关的不变量给出了图谱半径的界，得到了如下结论； ( 1 ) 给出了关于肛度的图谱半径的下界： 设连通图g 的顶点数为竹，b 度序列为( 呶( 1 ) ，血( f 1 ) ) ，则 p ( g ) 他o ) 等号成立当且仅当图g 是个拟正则图或拟半正则图，进一步， 艄= 恕雁需蕊鬻 利用所得到的结果，结合图的能量已有的结论，得到了图的能量的上界这 是论文的主要部分，已经发表在杂志瑶m a t c hc o m m u n m a t h c o m p u t c h e m 上 ( 2 ) 考虑一类特殊的图形即单圈图的谱半径的上界： 通过对一类特殊的单圈图的邻接矩阵进行运算，得出了这类图的邻 接矩阵的特征值的有关结果，从而得出单圈图的谱半径与度有关的一个 上界 i 硕士学位论文 关键词：邻接矩阵，度，髓度，谱半径，图的能量，单圈图 i i 图的度序列和谱半径的界 a b s t r a c t t h es e to fa l lt h ee i g e n v a l u e si sc a l l e dt h es p e c t r u mo fg r a p h s f o rm o s tg r a p h s w ec 蛆tc o m p u tt h e i re i g e n v a l u e sd i r e c t l y , e et h ee s t i m a t eo i lt h ee i g e n v a l u e so f g r a p h si s 缸a c t i v eq u e s t i o nf o rd i s c u s s i o n n o w a d a y s t h e r ea r em a n yr e s u l t sa b o u t t h eq u e s t i o n ，e s p e c i a l l yf o rt h eb o u n do i lt h es p e c t r a lr a d i u so fg r a p h s b u tf o rt h e l o wb o u n do nt h es p e c t r a lr a d i u s ，t h e r ea r ef e wa b o u ti t i nt h i sp a p e r ，w eo b t a i n t h a t ( 1 ) t h el o wb o u n dd e p e n d i n go i lt h ek - d e g r e es e q u e n c el l e tgb eac o l n o f i t e dg r a p hw i t hk - d e g r e es e q u e n c e ( d k ( 1 ) ，呶) ) t h e n p ( g ) 0 ) w i t he q u a l i t yi fa n do n l yi fgi sp 8 e u d o r e g u l a ro rs t r i c t l yp 8 e d 伽缸r e g i l l 脏，a n d p ( g ) 2 k 1 i m 。 1 ( 1 ) + d ：+ l ( 2 ) + + d t + l ( n ) ( 1 ) + 嚷( 2 ) + + ) f i n a l l yw em a k ea p p l yo ft h er e s u l t a n do b t a i na u p p e rb o u n do ft h ee n e r g y t h a ti st h em a i np a r to ft h i sp a p e ra n dh a sp u b l i s h e di n 誓m a t c hc o m - m u n m a t h c o m p u t c h e m ( 2 ) t h eb o u n do i lt h es p e c t r a lr a d i u so fe s p e c i a l 掣a 1 ) h 铲一u n i c y c l i cg r a p h s f h - s t l y , w eg i v et h ec o n c e p to fa l le s p e c i a lu n c y d i cg r a p h t h e nw eo b t a i nr o m e r e s u l t sa b o u tt h ee i g e n v u l u e so ft h ee s p e c i a lu n i c y c l i cg r a p h b yu s i n gt h e s er e - s u l t s ，u p p e rb o u n do i lt h es p e c t r a lr a d i u so fu n i c y c l i cf 叩h 8i so b t a i n e d k e y w o r d s ：a d j a c e n ym a t r i x ，s p e c t r a lr a d i u s ，d e g r e e ，k - d e g r e e ，e n e r g yo fa i i i 硬士学位论文 g r a p h ，u n i c y c l i cg r a p h i v 图的度序列和谱半径的界 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的研究成果除了文中特别加以标注引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写的成果作品对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明本人完全 意识到本声明的法律后果由本人承担 学位论文作者签名：厦鹱三a 唧年歹月荔日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，研究 生在校攻读学位期间论文工作的知识产权属湖南师范大学，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅本人授权湖南师范大学可以将学位论文的全部或部分内容编 人有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和 汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密口， ( 请在以上相应方框内打“、”) 作者签名：唐禳 导师签名。、夏们 4 1 日期：赫年f 月谚日 日期：固年，月 f 日 图的度序列和谱半径的界 第一章综述 1 1 引言 图论是一门内容非常丰富且应用十分广泛的数学分支，是近年来离 散数学和组合数学领域较为活跃的分支之一近年来，无论从其本身的 理论价值还是实际应用的广度和深度来看，图论及其应用的研究正处于 蓬勃发展的新时期图论的研究内容及其独特的研究方法，随着现代科 技的不断进步，越来越显示其独特的作用和魅力而图谱则是图论中的 一个新兴领域，它起源于理论化学家和物理学家为寻求一类偏微分方程 的近似解而建立起的一套离散的方法关于图谱的研究一直到2 0 世纪5 0 年代中期才渐渐出现在数学文献中 在此之前，尽管理论化学家是用不同的术语，但他们对图谱都非常感 兴趣经过短短几十年的发展，图谱已经成为了个系统的，综合的理 论分支它的研究与发展有着重要的理论和实际意义，它不仅促进和丰 富了图论和组合学本身的研究，而且在量子化学【1 4 ，冽、物理，计算机 科学f 6 】，通信网络即信息科学中均有广泛的应用其重要性主要体现在 以下几个方面【9 l ： 1 在量子化学中，某些不饱和碳氢化合物的结构是用图来表示的 已有的研究表明，在这样的分子里电子的能量级别就是其对应的分子结 构图的特征值另外，分子的稳定性和其他化学上的相关事实都与图的 谱和它所对应的特征向量有紧密联系 2 虽然图论和组合学的定理的陈述中并没有明确的提及到谱，但在 图谱的证明中有很多图论和组合学的定理正因为此，图谱已是图论和 组合学的一个重要工具 1 硕士学位论文 3 另外就是在计算机方面谱就是一组不变量的有限序列假设我 们感兴趣的信息在图谱中，这样可以用图谱来代替图，丽对应的有限序 列就很容易存入计算机中这样只要我们对很多类型的图可以利用有效 的方法求出它们的谱，就可以利用计算机进行方便有效地存储 正因为图谱有着广泛的应用，目前很多学者都在致力于这方面的研 究在本人所参阅的大量文献中，通常有以下三个主要的研究方向： 1 研究图谱和图的结构之间的关系，特别是“哪些图由它的谱确定” 同题，至上个世纪由理论化学家提出来后，已经取得不少成果，但用来 证明图的谱确定的工具似乎仅仅局限于证明某些特殊图形【1 1 ，3 8 ，3 9 】，如正 则图目前我们对谱确定图知之甚少 2 估计图的特征值，确定谱的分布图的特征值是图的同构不变量， 是图论特别是代数图论的一个重要的研究课题此外，图的特征值在化 学的分子结构研究中也有重要应用但目前对大量的图g ，还不能直接求 出它们的谱于是，对图的特征值的估计就成为了图谱理论相对活跃的 课题 1 1 4 1 一直很受学者的广泛关注 3 研究图谱和图的各种不变量之间的关系【2 , 8 ，9 】，这类问题也是理论 化学家很感兴趣的问题，现已有大量的研究成果 1 2 图论的基本概念 本文所研究的图均为无环无重边、有限无向的简单图设图g = e ) 的顶点集为v ( g ) = 口l ，地， ，i v l = 礼称为图g 的顶点数，又称为图g 的阶数；边集e ( g ) = e l , e 2 ， ， e l = m 称为图g 的边数若e 的两 个端点分别为顶点让与顶点。，记为e = ( 位，”) = 删，则称为顶点“与顶点 ”相邻接，记为u v n ( v ) 表示与顶点”相邻的所有顶点构成的顶点集 2 图的度序列和谱半径的界 与”关联的边的个数称为”的度，记为d ( n ) 图g 中的最大最小的 度数分别记为和j 以顶点”为起点长为奄的路的数目记为血( 。) ，又称 为点口的肛度显然有而( 口) = l , d l ( v ) = d ( ”) ，d + 1 ( v ) = 。也 ) 图g 的邻接矩阵记为a = a ( g ) = ( 叼) 。是一个nx 竹阶的( o ，1 ) 一方 阵，其定义如下：叼= ： 仉“码 l u 啡9 码 显然，n 。= 0 ，= 啄，敌而a ( g ) 是个实对称方阵我们称d e t ( z l a ) 为图g 的特征多项式记为p ( g ) 或p ( g ； ) 它的特征值记为a t ，k ，k ， 不妨将其由大到小排列为a l a ：k 称跏c g = a 。，a 2 ，k 为 图g 的邻接谱一般性，我们称a 。为图g 的邻接谱半径在不至混淆的 情况下，简称为图g 的谱半径，通常记为p ( g ) 本文所做的主要工作就是 对图的谱半径界的研究 此外，还有些未给出的专业术语与记号将分别在文中的相关章节里 给出或参阅【9 】 1 3 已有的结论 在参阅了大量的文献后，本人开始了对第二个同题的思考本文仅对 其中谱半径的界进行了研究对于图的谱半径界的研究，主要是利用图 的各种不变量，如图的顶点数、边数、度等下面介绍目前已有的结论； ( 1 ) 利用顶点数和边数： 关于图的谱半径界的研究，最早的工作是1 9 5 7 年c o l l a t z 和s i n o g o w i t z 给出的界： 定理1 3 1f 9 】设图g 为n 阶连通图，则 2 伽( 南) s p “) = n 1 3 硕士学位论文 其中下界当且仅当g 型r 时达到，上界当且仅当0 兰风时达到 特别是当g 是树时，有下述定理成立： 定理1 3 2 ( 9 】设g 为扎阶树，则有 p ( c ) sp ( k i 。一1 ) ；丽 上界仅在g 是星图硒。一，时达到 1 9 8 5 年，b r a u l d i 和h o f f m a a 给出了下面的界： 定理1 3 3 【3 】设图g 具有n 个顶点和m 条边，若。：掣，则 p ( g ) 一1 等式成立当且仅当g 掣凰u m k ) k 1 在1 9 8 7 年，s t a n l e y 改进了上面所给的界， 定理1 3 4 【3 3 】设图g 为扎阶简单连通图，其边数为m ，则 邸) s 型( - 1 华囹 等号成立当且仅当g 型k k u m k ) k 1 一般地，对于点数n 和边数m 的图，洪渊给出了更优的结果： 定理1 3 5 【2 0 】设g 为n 阶m 条边的连通图，则 p ( g ) 以i j 再了 等号成立当且仅当g 同构于下列两种图： 俐甄, n - l ；俐完全图玩 ( 2 ) 结合点数、边数，最大度及最小度： 1 9 7 2 年，h e i l m a i m 和l i e b 给出了树关于最大度的谱半径的上界： 定理1 3 6 【1 9 设图t 为n 阶树，则 p ( g ) 2 以f 1 4 里的度序列和谱半径的界 1 9 8 8 年m i n c 给出了关于点数边数、最大度及最小度的谱半径的界s 定理1 3 7 1 3 0 】设g 为n 阶m 条边的连通图，d 是g 中点的最小度数， 是g 中点的最大度数，则 6 s 娑p ( g ) t l 。+ 等式当且仅当g 为正则图 扈生彪引入图g 的最小度6 ，在一定条件下改进了上述定理； 定理1 3 。8 陋1 设g 为n 阶m 条边的连通图，6 是g 中点的最小度数， 则 “g ) 以元= 彳厕 等号成立当且仅当g 为t l 一2 阶正则图 2 0 0 1 年，洪渊、束金龙和万坤夫又一起改进了这一个定理： 定理1 3 9 【2 1 1 设g 为n 阶m 条边的连通图，5 是g 中点的最小度数， 则 邸) 坐堂写圃 等号成立当且仅当g 为正则图。或顶点度为6 或b 一1 的二度图 显然在上面所给的定理中分别取5 = 0 或j = 1 即可得到定理1 3 4 和 定理1 3 5 在2 0 0 4 年，s t e v a n o v i 也是利用顶点数和图的最大度，得出了下面的 结论( 见【1 3 】) t 定理1 3 1 0 【3 4 i 设图g 为竹阶连通非正则图，最大度记为a ，则 删曼一丽研1 7 t 1 一jj l r 类似地，d a s 和k u m a r 也得出了下面的结论； 5 硕士学位论文 定理1 3 1 1 【1 0 】设g 是简单连通图，和6 分别表示中点最大和最小度 数，则有 p ( g ) 、2 m 一( n 一1 ) j + p z ) a 等号成立当且仅当g 是正则图或星图 ( 3 ) 利用与度相关的不变量： 在1 9 8 0 年c v e t k o v i d ，d 0 0 b 和s a c h s 利用度序列给出下列的结果t 定理1 3 1 21 9 j 连通图g 的度序列为d ( 1 ) ，d ( 2 ) ，d ( 哟更l j 肭、7 巴e yd 2 ”) p ( g ) v 型等旦 等号成立当且仅当图g 为正则图或半正则图 2 0 0 1 年，b e r m a n 和z h a n gx i a o - d o n g 给出了一个关于度序列的上界： 定理1 3 1 3 【1 】1 设图g 为n 阶连通图，g 的度序列为d ( 1 ) d ( 2 ) d ( n ) ，则 p ( g ) 啪薹 d ( t ) d u ) 等号成立当且仅当g 为正则图或半正刘偶图 2 0 0 4 年束金龙、吴雅蓉又进一步改进了谱半径的界，得到一下定理： 定理1 3 1 4 3 2 】设g 为佗个顶点的简单连通图，不妨设其顶点度满足t d ( 1 ) d ( 2 ) d ( n ) ，则 “g ) s 垡( 尘二! 兰丛亘匡 三至三 耍三三堑至噩囹( 1 墨t 进一步，当i ；1 时，等式成立当且仅当图g 是正则图当2 is1 1 时，等式成立当且仅当图g 满足：d ( 1 ) = d ( 2 ) 一d ( i 1 ) = ，l 一1 且 d ( t ) 一一d ( n ) = j 的二度图 随后，y u ：a 、l u m 和t i a n f 利用相关的度序列得到了下面的界： 6 一 图的度序列和谱半径的界 定理1 3 1 i 【3 7 1 设连通图g 的度序列为d ( 1 ) ，d ( 2 ) ，d ( t 1 ) ，则 掀傈臻磊孺 等号成立当且仅当图g 是一个拟正则图或拟半正则图 1 4 本文的主要工作 目前，关于图谱半径的界已有较多的研究成果，但大部分都是关于其 上界的本文主要利用相关的度序列得到了图的下界，进一步，本人利 用此结果得到了图的能量的上界此外本人还用相关的度序列得到了一 类特殊图一单圈图的谱半径的上界，并且举例对这个所给的界与前面 的结论进行了比较 本文具体安排如下t 在第二章，给出并证明了如下的结论：设连通图g 的顶点数为竹，k 度序列为d k 0 ) ，比( n ) ，则 烈g ) 伪0 ) 等号成立当且仅当图g 是一个拟正则图或拟半正则图进一步， 邸，= 规端脊辫错 利用所得到的结果，结合图的能量已有的结论，得到了图的能量的上界 在第三章中，考虑一类特殊的图形一单圈图通过对一类特殊的单 圈图的邻接矩阵进行运算，得出了这类图的邻接矩阵的特征值的有关结 果，由此得出单圈图的谱半径与度有关的一个上界： 7 须士学位论文 伊表示到圈上的顶点距离最长为k 的单圈图，傩- + t 表示距离圈上 顶点的最短距离为ju = 1 ，2 ，k ) 的所有顶点的最大度，则a l ( a ( 伊) ) a 2 k ，所对应的特征向量为x l j 她，x 。 一1 5 硕士学位论文 则x l ，x 2 ，x 。构成r n 中的正交基，令j = f 巩x ，则巩= j t x i ，( i = f f i l 1 ，2 ，n ) 为了证明3 i mf ( 2 k ) 2p ( g ) ，l l p e 8 y j 了罚蒜趋向于a 2 ( c ) 的特 征值矿( g ) 所对应的单位特征向量佧一。) 又因为 d 2 kaa勺 一v ，| = 了夏霜i 雨= 瓦孑瓦两 鸫= 巩x t = 巩舻x t i = 1i = 1 则有 n 磙( ”) = 鳄a 尹 如果图g 是非二邵图，因为0 1 0 且 l i a d ( i = 2 ，3 ，n ，) 则 l i r a 粤： x t , = l ， 。出、让 【0 ， i 1 、毋a 箩 ti = l 所以向量了刁趋向于x t ，可知结论成立 如果图g 是二部图，因为0 i 0 且a l l 九1 0 = 2 ，3 ，n 一1 ) ，k = 一a l ， 卿i l i m 墼： 一* 銎l 鲜a 哥 竖，i ：1 加阳i 。 0 1 唧+ 1 ) 由于佻o = ( d k _ j + 1 1 ) n t 一抖i ，j = l ，2 ，七，所以如果j 圣一n ，则啷= + 1 2 7 硕士学位论文 定理3 3 1 令岛( a ) = 1 ，毋( a ) = a ， 毋( a ) = a 毋一t ( a ) 一专尹岛一。( a ) ， d = 2j 3 ，后一1 ) ， ( 壮( 川c o s 望笔) 钆( 犷i k - 1 ( n 则： ( 1 ) d e t ( a i a ( g ) ) = 罂l s ( a ) n j n 紫- - n j + l ( a ) ( 3 3 2 ) ( 2 ) a ( g ) 的谱 矿( a ( g ) ) = ( 屿。n a ：8 j ( x ) = o ) u ( u 。f l ，。】 a ：嚣( a ) = o ) 证明；假设岛( a ) 0 ，0 = l ，2 ，一1 ) 令m = d e t ( a i + a ( g ) ) ，则由引理 3 2 3 可得 a = a = & ( a ) 0 岛= a 一磊n l 鬲1 = a 一五n l 酉1 两 ：字：湍舢。面尹2 莉刘 类似可得 一百蕊 、n ，一1 岛- 2 ( a ) 卜i 骊 a 岛一- ( a ) 一等岛一。( a 1 五两一 器0 ，纠，2 i 2 8 凼此 级+ 。嘲掣= 器+ ：c o s 掣 踯) + 2 c o s 掣踮 一 瓯一1 ( ) ( a + 2 c o s 塑半) ( 妒i n k - 1 踽( 对 = _ _ _ _ 。 _ 。 。_ 。_ - 。 ：壁盟 所以由引理3 2 3 知 a e t ( 舡+ a ( g ) ) = 删粼粼赡。器 = 硭l 掣( a ) 啄n 掣一( ) 又由( 3 3 1 ) 式可知d e t ( 舡+ a ( g ) ) = d e t 一a ( g ) ) ，所以对满足毋( a ) o u = l ，2 ，七一1 ) 的a 有等式d e te i a ( g ) ) = 罄1 s ( a ) 码印夥一唧+ 1 ( a ) 成立，又因为d 甙( 姐一a ( g ) ) 是一个有限次多项式，故该等式对任意的入 都成立由此显然易得( 2 ) 成立口 令矩阵g 为k 七阶对称三对角块矩阵 g = 0 撕l f l 撕f 习0 析f 玎 撕f i 。 。 d v 五- i - 1 d x 石- x - 10 析f 了 胛2 嘲! 坐型 讥 引理3 3 1 砖j = l ，2 ，七一1 ，令g j 表示g 的j j 阶前主子矩阵( 即 前j 行，j 列构成的主子矩阵) ，则 d 酏( m g j ) = 易( a ) ，j = 1 ，2 ，七一1 ， 2 9 硕士学位论文 证明：令 q k = d e to i g ) = 嚣( a ) o l6 l b ld 2 幻 令q j 表示q k 的j j 阶前主子矩阵，则有递推公式【3 5 】 q o ( a ) = 1 ，q l ( a ) = = a d l ， 且 q j o ) = q 一曲q j l ( a ) 一碍一lq i 一2 ( a ) ( 3 3 3 ) 可以砜= 垆一d k - 1 = 0 , a ( k t ) = 2 镧掣加厚扣1 ，一 1 ，代入( 3 3 2 ) 式即得到d e t ( h g j ) = s j ( a ) ，o = l ，2 ，k - 1 ) ，d e t ( a i g ：f ) ) = 露( a ) 由上面引理可得a ( g ) 的谱口( a ( g ) ) = ( u j 印口( g j ) ) u ( u t 。i l ，叫口( g ) ) 又因为q 是g 0 的j j 阶前主子矩阵，所以由插值定理和比较定 理( 见【5 】) 得a ( g ) 的谱半径a l ( a ( g ) ) 矿( g 0 ) 口 由引理3 2 2 可知， 定理3 3 2 图g 表示层数为的单圈图心引，则 l ( a ( 伊) ) 蚴 盟 锕1 + 、瓦j ，狮_ i + 2 对于任意的单圈图，由引理3 1 1 可知： 一3 0 圈的度序列和谱半径的界 定理3 3 3g k 表示层数为c 的单圈图，饥一州表示距离圈上顶点的最短 距离为j0 = 1 ，2 ，七) 的所有顶点的最大度，剜 a - ( a ( 伊) ) m 戤 鲤搿而j + 而j ，佤i + 2 证明：g 表示圈的顶点数等于g t 的圈的顶点数的单圈图，且对应的 每一层顶点的度数均为茁g = l 2 功，显然舻是g 的子图，所以 a t ( a ( 俨) ) a l ( a ( g ) ) 由于 1 ( a ( g ) ) 口( g ) ，所以由引理3 , 2 2 得 a 一( a ( g ) ) 嗽 跋 佤j + 丽，6 j + 2 ， 所以a l ( a ( ) ) z z z a x z z 垴, x 3 j k v 啄= 1 + 再 ，订乒_ r + 2 口 3 4 注记 在这小节中将会把上面所得到的界和已有的界进行比较： 如在下面所给的图3 - 2 ，其层数为3 , 3 1 = 1 , 7 2 = 3 ，加= 5 ，n = m = 1 7 ，其 上界可以通过求如图3 所示单圈图的谱半径的