（基础数学专业论文）图的特征值的界.pdf

摘要 图的谱理论是图论研究的重要领域之一，也是一个非常活跃的研究领域，它在 量子化学、物理、计算机科学、通讯网络及信息科学中都有广泛的应用图谱理论 的研究主要是利用成熟的代数理论和技巧，并结合图论和组合数学的理论来研究图 谱及其与图有关的结构性质，图的其他不变量之间的关系，将图与网络的代数性质 与图的拓扑性质紧密地联系在一起 本文分三部分集中反映了作者几年来围绕图谱所做的工作以及取得的主要结 果 在文章的第一部分中主要围绕平面图的谱半径的研究展开我们利用矩阵理沦， 得到了图的谱半径的可达上界，同时也刻画了达到上界的极图 在文章的第二部分中，我们研究了n o r d h a u s g a d d u m 图类的谱半径的上界，即 图与其补图的谱半径之和( 积) 的上界，利用图的色数和谱半径的上界给出了它的 j l 个上界 在文章的第三部分中，我们研究了图的拉普拉斯极限点的问题证明图的第k 个 大的拉普拉斯特征值的极限点一定是图的第k + 1 个大的拉普拉斯特征值的极限点， 图的第k 个小的拉普拉斯特征值的极限点一定是图的第k + 1 个小的拉普拉斯特征值 的极限点，并且给出了图的第k 个大的拉普拉斯特征值的极限点的最小值和图的第k 个小的拉普拉斯特征值的极限点的下界 关键词：图的邻接谱；n o r d h a u s g a d d u m 图类；图的拉普拉斯潜：极限点 中图分类号：o l5 75 a b s t r a c t t h et h e o r yo fg r a p hs p e c t r ai sn o to n l ya ni m p o r t a n ta r e ai ng r a p ht h e o r yb u ta l s o a 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 ni nt h ef i e l d so fq u a n t u mc h e m i s t r y ， p h y s c i s ，c o m p u t e rs c i e n c e ，c o m m u n i c a t i o nn e t w o r k a n di n f o r m a t i o ns c i e n c e t h et h e o r y o fg r a p hs p e c t r ac a nb ec o n s i d e r e da sa na t t e m p tt od i s c o v e rt h ep r o p e r t i e so ns t r u c t u r e so f g r a p h sa n dt h er e l a t i o n sb e t w e e nt h es p e c t r aa n df i x e dv a r i a t e so f g r a p h sb ym e a n so f t 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 eo fa l g e b r a ，t h e o r i e so fg r a p ha n dc o m b i n a t o r i c s s o a st oe s t a b l i s h sf i r me s s e n t i a lr e l a t i o nb e t w e e nt h ea l g e b r a i cp r o p e r t i e sa n dt o p o l o g i c a l p r o p e r c i e so fg r a p h sa n dn e t w o r k s t h i st h e s i s ，i n c l u d i n gm a i nr e s u l t so nb o u n d sf o re i g e n v a l u e so f g r a p h sw h i c hc a n b es e p a r a t e dt h r e ep a r t s p a r t1s o m er e s u l t so nb o u n d sf o re i g e n v a l u e so fg r a p h sa r eg i v e n p a r ti iw eg i v e ns o m e u p p e r b o u n d saf o r t h e s p e c t r a l r a d i u so ft h e n o r d h a u s g a d d u mt y p e p a r ti i iw eg i v e ns o m ep r o p e n t yf o rl a p l a c i o nl i m i tp o i n t k e y w o r d s ：a d j a c e n c ys p e c t r a l ；n o r d h a u s - g a d d u mt y p e ；l a p l a c i o ns p e c t r a l ；l i m i tp o i n t c l cn u t u b e r s 015 7 5 引言 引言 图沦是一门应用广泛的数学分支，是处理离散数学问题的强有力的工具图论同 时也是运筹学、电路网络、通讯网络、计算机科学理论研究和实践应用中不可少缺 的数学工具不仅如此，在开关理论、编码理论、计算机辅助设计，甚至于社会科学、 化学、物理等领域都有广泛的应用，因而无论就图论的理论价值，还是其实际应用 的广度和深度来看，图论及其应用的研究正处于一个具有强大生命力的蓬勃发展的 新时期图论的研究内容及其独特的研究方法，随着现代科技的不断飞速发展越来越 显示出其独特的作用和魅力 图的谱理论是图论研究的重要领域之一，也是一个非常活跃的研究领域，它在 量子化学、物理、计算机科学、通讯网络及信息科学中都有广泛的应用自从2 0 世纪 5 0 年代l m l i h t e n b a u m 和l c o l l a t z ，u s i n o g o w i t z i ”被认为是开创性文章发表以来， 对图谱理沦的研究不断发展和深入，这方面的大量研究成果相继发表在国内外的许 多重要学术刊物和专著中旧”真实早在1 9 3 1 年，eh c k e l 等理论化学家们就对图的 谱理论产生了浓厚的兴趣，并着手进行了研究尽管他们所采取的符号和术语与现代 数学家所用的不一致，但是却大大推动了图谱理论的研究正因为诸多的组合、图论 和代数等方面的数学家( 如a j h o f f m a n ，c d g o d s i l ，r a b r u a l d i ，r ，e s t a n l e v ， l l o v a s z ，n a s h - w i l l i a m s ) 以及理论化学家、物理学家( 如a t b a l a b a n ，a s t r e i 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 在沦及图 谱时讲到：“有些其特征上是纯组合的主要结果有这样奇妙的特性，即如果不借助涉 及图的邻接矩阵的特征根的代数方法，是不可能得到现存所知的结论的” 经过数十年的研究，人们对图谱理论的认识已经相当广泛和深入了图谱理论所 研究的对象主要包括图的邻接谱、拉普拉斯谱、b 一陪、q 一谱等，其中对邻接谱、拉 普拉斯谱的研究最为普遍尽管图谱理论呈现出非常丰富多彩的形式，但各种不同定 目的特征根的界 义的普之间还是有着相互联系的 设g 为 阶图，a ( g ) 为邻接矩阵，d ( g ) 是以g 的顶点度为对角元的对角阵令 ( 丑，) = d e t ，+ d ( g ) 一爿( g ) ，通过对参数旯，取不同的值，就可以将上述各种 谱的特征多项式都用晶( 五，) 来表示 邻接谱的特征多项式： j d ( g ；五) = d c t ( a l 一爿( g ) ) = 吒( 五，0 ) ； l a p l a c i o n 潜的特征多项式： j i ) ( g ；五) = d e t ( 2 1 一( d ( g ) 一爿( g ) ) = ( 一1 ) “尼( 一五，1 ) ： f r k c h u n g 定义的l a p l a c i o n 谱的特征多项式： p ( g ；2 ) = d e t ( 2 1 叫一d ；a ( g ) d ；) = 并鲫，1 叫； ) =一( 一 2 2 ) = 二i 圭 屹( o ，一丑) ； q 谱的特征多项式： q ( g ；2 ) 2 南d e t2 d - a d e t ( e d - a ) = 南肿，饥卜商商蹦0 ； c 一谱的特征多项式： c ( g ；兄) = d e t ( 2 1 ( d ( g ) + 爿( g ) ) = ( 五，一1 ) s 潜的特征多项式： s ( g ；丑) = d e t ( 2 1 一j + ，+ 2 a ) = ( 一1 ) “2 ”( 一掣，o ) 1 其中j 为全1 矩阵，g + 为“广义图”，其“邻接阵”为a 一j 尤其当g 为k 正 则图时，这些谱之问有确定的数量关系，只要求出其中一种，便能很快求得其它各 种形式的谱尽管这些林林总总的谱都能化到e i ( 五，) 形式，但一般来说，很难确定， 而且也掩盖了各种不同谱的应用背景和实际价值，所以各种不同谱的研究仍很必要： 同时也给图谱理论的研究提供了广泛的题材和丰富的内容到目前为此，至少有5 本 号著( n lb i g g s ，d c v e t k o v i c ，m d o o b 和h s a c h s “，1 g u t m a n 和a t o r g a s e v ， f r k c h u n g 和jj s e i d e l ) 较全面地收集了这方面的主要结果 在国内，李乔和冯克勤最早开始图谱理论的研究，他们的文章“论图的最大特 征值”( 应用数学学报，1 9 7 9 ，1 6 7 1 7 5 ) 是国内图谱理论研究的重要文献之一随后， 张福基，李炯生，柳柏濂，洪渊等人在图谱理论的研究方面都取得了许多重要且优 美的结果 日i言 本文分三部分集中反映了作者几年来围绕图谱所做的： 作以及取得的主要结果 第一章主要围绕平面图的谱半径的研究展开在第一节中，我们综述了般图类 谱半径的已有结论，同时也描述了平面图谱半径上界改进的历程在第二节中，我们 利用矩阵理沦，得到了图的谱半径的可达上界： 定理1 1 若n 阶简单图g 有研条边，则 p ( g ) s ( m 扛丽j 丽了面) 等号成立当且仅当g 是正则图或星图k 。 定理1 2 若g 是简单连通图，则有 p ( c ) 2 一n + l 一( 占一o ( n l 一) 等号成立当且仅当g 是正则图或星图g 兰k i 。 定理1 3 若g 是有聊条边 阶连通图，则 pfg)s6-1+x(6+1)：+4(2m-sn) 2 等号成立当且仅当g 是正则图足。或星图 在本文的第二章中，我们主要研究了n o r d h a u s g a d d u m 图类的谱半径的界我们 利用图谱半径的新结果，结合谱半径与色数之间的关系，得到图与其补图的谱半径 之和p ( g ) + p ( g 。) 的几个上界： 定理2 2 若 阶简单图g ，色数为k ，且g 。无孤立点，月2 2 则 厂彳 尸( g ) + ( g 。) 、( 2 ) ( 一1 ) 2 一万一2 一) 】 定理2 3 对于任意有州条边的图g ，有 p ( g ) + p ( g 。) s 一1 + l 十2 n ( n 一1 ) 推论2 1 对于任意图g ，有 1 尸( g ) p ( g 。) ( 1 十”( ”一1 ) 1 + 2 n ( n 1 ) ) 定理2 4 设 阶简单图g 有m 条边，若g 与g 。都无孤立点，则 p ( g ) + p ( g 。) 4 2 ( 一1 ) ( 一2 ) 推论2 2 没g 是n 阶简单图，且g 与g 。都无孤立点，则 p ( g ) p ( g c ) 茎坠娑塑 2 定理2 5 对h 阶连通图g 与g ，有 图的特征根的界 p ( g ) 十p ( g ) 一l + 、肝五万酉j 丽而 等式成立当且仅当n = 4 t + l ，f 为非负整数，且g 是孚= 2 f 阶正则图 定理2 6 若胛阶简单图g 及其补图g 。的色数分别为k 与万，则 邸抑( 、。 曩( 2 - 1 苇- 1 ) n ( n - 1 ) 等式成立当且仅当g 兰e 或空图 在本文的第三章中，我们研究了图的拉普拉斯特征值的极限点，我们将证明图 的第k 个大的拉普拉斯特征值的极限点一定是图的第k 十1 个大的拉普拉斯特征值的 极限点，图的第k 个小的拉普拉斯特征值的极限点一定是图的第k + 1 个小的拉普拉 斯特征值的极限点，并且给出了图的第k 个大的拉普拉斯特征值的极限点的最小值和 图的第k 个小的拉普拉斯特征值的极限点的下界 在介绍后面几章内容之前，先将阻后经常用到的基本概念及记号预先做一介绍 本文所研究的图均为简单无向图g = ( 矿，e ) ，用v = v ，v ：，v ，) 表示圈g 的顶点 集，g 的顶点个数l v ，? 称为图g 的阶数，有时也用v ( g ) 表示图g 的阶数， e = k ，p ：，e 。) 表示图g 的边集，l e m 称为图g 的边数，也记为s ( g ) 如果顶点、o 是边p ，的一个端点，则称与e j 关联，与q 关联的边数称顶点为q 的度，记作 如( v ) = d ( 一) = d ，若边( v ，v ，) e ，则称顶点q 与v ，相邻接记作v i a d j r ，而v i r l a d j y ) 则表示h 与v ，不邻接，即边( u ，v ，) 不在e 中图g 的最大度、最小度分别记为a ( g ) 和 j ( g ) ，简记为和jd ( _ ，v ) 表示v 与v ，两点问的距离，d 或d ( o ) 表示图g 的直径 在图论中，有几类简单图十分重要，k 表示n 阶完全图，k ，表示孤立点，尸 为 阶路，g 表示 阶圈，? ：表示n 阶树，k 。表示具有( k ，k ) 二划分的完全偶图，且 l k 卢p ，户g ，特别地k 。称为星图g 表示图g 的补图，是指和g 有相同顶点集， 在g 。中两个顶点相邻接当且仅当它们在图g 中不邻接有时也用6 表示图g 的补图 下而再给出与图谱有关的定义及记号 n 阶简单图g = ( y ，e ) ，其顶点集为v = u ，v 2 ，) ，e = 她，e 。，) 记 a = ( “。) 为图g 的邻接矩阵，其中 铲淼 显然一是主对角线元都为0 的月阶实对称矩阵，a 的特征多项式称为图g 的特征多项 式，记为p ( g ；2 ) ，也即p ( g ；a ) = i2 1 一a i 引言 由于a 为实对称矩阵，所以a 的特征根都是实数，故可从大到小排列为 a ( g ) t 2 ( g ) - 屯( g ) 五( g ) 称为g 的第g 个大根特别地称 ( g ) 为图g 的谱半径，记为p ( g ) 称矗( g ) 为图 g 的最小特征根 顶点叶的度为吐( j ：1 ，2 ， ) ，则称矩阵d ( g ) = d i a g ( d i ，d 2 ，以) 为图g 的度矩 阵，矩阵，则矩阵上( g ) = d ( g ) 一a ( g ) 为图g 的拉普拉斯矩阵，显然它是胛阶实对称 矩阵，它的特征值称为图g 的拉普拉斯特征值，由于l ( g ) 是半正定的实对称矩阵， 所以它的特征值可依次记为 i ( g ) 2 ( g ) 以( g ) = 0 或 0 = j ( g ) s ；( g ) ，( g ) “( g ) 为图g 的第k 个大的拉普拉斯特征值，从( g ) 为图g 的第k 个小的拉普拉斯特 征值我们称实数r 为图的第k 个大的拉普拉斯特征值的极限点是指：如果存在图序列 g j ，使得4 ( g , ) 段( g j ) 且l i m k ( q ) = ，我们定义下面的集合 l k = p ：r 是图的第k 个大的拉普拉斯特征值的极限点 l 净p ：r 是图的第k 个小的拉普拉斯特征值的极限点) 还有一些未能详细介绍的概念和记号可在相应的章节中再详细介绍或可参阅文献 1 】， 3 等有关图论方面的书籍 圈的特征根的界 第一章图的谱半径的上界 1 1 引言 本章我们主要研究平面图谱中，一般图类的谱半径界的问题首先我们先对已有 的研究成果做一综述 图谱理论的先驱l c o l l a t z 和u s i n o g o w i t z 于1 9 5 7 年给出了一般图类的可达上、 下界 若g 为”阶连通图，则 2 c o s 三户( g ) ”一1 左边等号成立当且仅当g 兰只，右边等号成立当且仅当g 兰k 时隔十年后的1 9 6 7 年，h s w i l f 首次将图的谱半径与图的色数建立了联系，得 到另一个可达下界： 图g 的色数k 与谱半径p ( g ) 满足， k p ( g ) + 1 对连通图等弓成立当且仅当g 兰k 或g 为奇圈 同时他还得到一个p ( g ) 的可达上界： 若g 为”阶图，有m 条边坝0 邸) s j 2 m ( 1 去) 等号成立当且仅当g 兰吒 n o s a l ，l o v a s z 和p e l i k a n 各自独立地证明了谱半径与反映图的结构特点的最大 度建立了联系： p ( g 1 1 9 7 2 年，d c v e t k o v i c 证明了h 阶图的谱半径n ( a ) 与其色数k 满足： p ( g ) 掣。 1 9 8 3 年，cs e d w a r d s 和c h e l p h i c k 给出： 若g 为月阶图，有m 条边，且其色数为 贝0 p ( g ) 2 m ( k - 1 ) 1 9 9 5 年，洪渊”指出了等式成立当且仅当g 为完全多部图并给出了这一结论的 简单证明 在随后的近十年中，有关图的谱半径的研究取得了很多结果 r a b r u a l d i 和a j h o f f m a n 证明了： 第一章图的谱半径的上界 若m = ( ! 】，则p ( g ) 兰七一1 ，等式成立当且仅当g 为k 与孤立点的并，即 g = k ku ( h k ) x s f r i e d l a n d 将上述结论推广为 耗地川，则 p ( g ) 一1 + 派而 2 r r s t a n l e y 于1 9 8 7 年证明了： 对于任意有m 条边的”阶图g ，有 邸) 扣+ 厮) 等号成立当且仅当m且g = k 。u ( n k ) k 1 9 8 8 年，洪渊得到了： 若g 是有研条边月阶连通图，则有 p ( c 、- , 2 m ”+ 1 等号成立当且仅当g 是完全图k 或星图k 。 很容易将上述结论推广到： 若g 为h 阶无孤立点图，有m 条边，则有 p ( g 1 4 2 m n 十l 等号成立当且仅当g 的个分图为星图或完全图，其它分图为足， 若g 为”阶图，有m 条边，个孤立点，则 p ( g ) 2 脚一 + ，+ 1 等号成立当且仅当g 有，个孤立点，且g 的一个分图为星图或完全图，其它分图为彪， 对任一n 阶图g ，若d l ，d ：，z ，为度序列则 邸) 艟印 比该结论更一般的形式为 p ( g ) 二以d ， m ( f 磊e 利用矩阵论和图的特点很容易证明： j 堡p ( g ) z a 等号成立当且仅当g 为正则图 图的特征根的界 p ( c ) , d l d 2 等号成立当且仅当g 为正则图或星图，其中d l ，d z 为图g 的最大、次大度 1 9 9 8 年曹大松给出了一些结论的统形式： 若g 为连通图，最大的2 度记为t ( g ) ，则有 p ( a ) , i t ( g ) 等号成立当且仅当g 是正则图或星图并上e 或完全图并上度较小的正则图其中 t ( c ) = m a x d r ”矿( g ) ) 其中d 52 表示v 的2 一度，即 可2 ) ：d j 同年，洪渊还证明了： 小4 6 若g 是有m 条边竹阶连通图，且每对顶点至少有，个公共邻点_ 贝0 p ( g ) 型型堕婴型 等号成立当且仅 - kg 是完全图k 。或星图k 。 洪渊和柬会龙叉证明了： 若g 是有r r l 条边r t 阶连通图，则 邸) 生型坠婆堂坠盟 等号成立当且仅当g 是正则图k 。或星图k 。 在本章中，我们给出了图的谱半径的几个可达上界： 定理1 1 若g 是n 阶简单连通图，则有 邸) s 毒( _ l + 再丽砀丽) 等号成立当且仅当g 是正则图或星图k 。 定理1 2 若g 足月阶简单连通图，则有 p ( g ) , j 2 m 一月+ 1 一( j 一1 ) ( 一1 一) 等号成立当且仅当g 是正则图或星图g 兰k h 。 1 2 图的谱半径的上界 引理1 1 4 1 ：对于任意有m 条边的f 阶图g ，有 第一章图的谱半径的上界 p ( g ) 告( 一1 + 而) 等号成立当且仅当m = ( ： ，且g = k u 。一的 引理1 2 ”l ：若g 是有m 条边n 阶简单连通图，则有 p ( g ) 压而 等号成立当且仅当g 是完全图瓦或星图k i 。， 定理1 1 对 阶简单连通图g ，有 邸) 专( _ l + 正丽面丽) ( 1 ) 等号成立当且仅当g 是正则图或星图k i 。 证明设= ( x l ，x 2 ，) 7 是邻接阵a 的对应与晟大特征值p ( g ) 的单位特征向 量，a 1 是a 的第f 行向量，x ( o 是- + y o 向量，它的第，个分量当v 和v j 相邻时为x ， 不相邻时为0 ，则显然有 a j x ( i ) = a j x = p ( g ) x ( i 、 ( 2 ) 所以利用柯西许瓦兹不等式有 p 2 ( g ) x ? - 3 时，都有2 ( 一1 ) 一2 ) 一1 + 1 + 2 n ( n 一1 ) ，也即定理2 4 比 定翌目2 3 墨好 图的特征根的界 i 司理，利爿j 定理1 3 司得： 定理2 5 对h 阶连通图g 与g 。，有 p ( g ) + p ( g 。) 一1 - t - l - i - 2 n ( n 1 ) 一4 6 ( n 一1 一) 等号成立当且仅当 ：4 t + 1 ，f 为非负整数，且g 是与：2 t 阶正则图 证明由定理1 2 得 户( g ) 去( 1 + 再丽j 丽而i ) p ( 6 。) * 1 + 肛丽巧：丽) ( 3 ) ( 4 ) 其中而：型业一为。阶图g 的补图g c 的边数，否- = n - 1 一与五：。一1 一占分别为 2 ”阶图g 的补图g 。的最小度和最大度 p ( g ) + ，) ( a o ) 丢( 一l + i ；i i f 二百孑i i 丽) + 圭( 一l + i ；i i f 二i 否i i 二i 二面) 叫+ x 堕1 + 8 m 至- 4 巫6 ( n - 1 - a ) + x 堕1 + 4 巫n ( n - 互1 ) - 互8 m - 巫4 8 ( 巫n - 1 - a ) 2 f ( x ) ：一1 + # 1 + 8 x - 4 6 ( n - 1 - a ) + x 1 + 4 n ( n - 1 ) - 8 x - 4 f i ( n - 1 - a ) ， 当。：丛旦尘时达到极大值 厂( 堕等尘) ：_ 1 + x l + 2 n ( n - 1 ) - 4 f i ( n - 1 - ) 所以 p ( g ) + 尸( g 。) 一i + r ；j i 石_ 二巧_ = i i 琴石_ 两 要使等号成立必须有堕等尘为整数，又堕等坐正好是”阶完全图的边数的一 半，而且要使等号成立，必须有( 3 ) ，( 4 ) 都成立，也即g 与g 。都是正则图，所以 必须有g 与gc 都是n - 2 ：2 t 阶正则图 定理2 6 若阶蔷单图g 及其补图g c 的色数分别为女与云则 尸( g ) + p ( g ) , v ( 2 肛- l - 2 a ) n ( n - 1 ) 等式成立当且仅当g 兰k 或空图 证明由引理25 得 椰2 ( k 二k l 叵) m = 缸巧 及 艄 j 半= 扣一 第二章n o r d h a u s g a d d ur n 留类的谱半径的上界 其中历：丛竺一卅为 阶图g 的补图g c 的边数，f 为图g 的补图g c 的色数设 5 ：】一1 女，；：l 一1 石从而 p ( g ) + p ( g 。) 曼以丽+ 靠石面丽 拭椭只有当m 2 南咖_ 1 ) 时取是竺堕翌，删 p ( g ) + p ( g 。) v2 - 1 t - 1 p ) ( n - i ) 等式成立当且仅当g 和g 。是空图或等完全k 部图另外由用= = 七月( 月一1 ) 得g 必 2 ( s + s l 须是元全图或至图 该结论不仅具有完美的对称性，而且是利用色数来反映p ( g ) + p ( g 。) 的可达上界 同时， c = j z 去 均小- t 、压 圈的特征根的界 第三章图的拉普拉斯特征值的分布 3 1 引言 阶简单图g = ( 矿，f a ，其顶点集为v = “，1 2 ，v 。) ，e = ( 8 ，p ：， ，d i 为顶 点_ 的度，i e a ( g ) = ( d 。) 为图g 的邻接矩阵，d ( g ) = d i a g ( d l ，d 2 ，以) 为图g 的度 矩阵，则矩阵l ( g ) = d ( g ) 一a ( g ) 为图g 的拉普拉斯矩阵，显然它是，? 阶实对称矩阵， 它的特征值称为图g 的拉普拉斯特征值，由于上( g ) 是半正定的实对称矩阵，所以它 的特征值可依次记为 f l ( g ) i u 2 ( g ) 。( g ) = 0 或 0 = “( g ) ；( g ) 妄以( g ) 肼( g ) 为图g 的第k 个大的拉普拉斯特征值，以( g ) 为图g 的第k 个小的拉普拉斯特 征值 关于图的拉普拉斯谱的研究是仅次于邻接谱的研究的重要课题，而且也得到了 许多非常优美的结果 关于极限点的研究是始于a h o f f m a n l ，他于1 9 7 2 年给出了在闭区间 【2 ，4 2 + 5 】内的图的邻接谱的最大根的所有极限点，并证明了小于2 的任一实数均 不是图的最大根的极限点1 9 8 9 年，j b s h e a r e r 为庆贺a jh o f f m a n 的6 5 华诞时发表 的论文证明了任一个超过f = ( 1 + 5 ) 2 的实数均可为图的最大特征根的极限点所以 关于图的邻接谱的最大根的极限点的分布已经完全清楚了至于图的第二大根的极限 点的研究有d c a o 和y h o n g 的一篇文章2 1 ，他们证明了第二大根的最小极限点为 1 3 ，其他根的极限点的讨论几乎没有看到本文讨沦了图的拉普拉斯谱的极限点的性 质，并且给出了图的第k 个大的拉普拉斯特征根的极限点的最小值 我们称实数r 为图的第k 个大的拉普拉斯特征值的极限点是指：如果存在图序列 g ，使得“( g ，) 以( g j ) 且l i m 段( q ) = ，我们定义下面的集合 l k = p ：r 是图的第k 个大的拉普拉斯特征值的极限点) 丘= ，：，是图的第k 个小的拉普拉斯特征值的极限点) 我们将证明图的第k 个大的拉普拉斯特征值的极限点一定是图的第k + 1 个大的拉普 拉斯特征值的极限点，图的第k 个小的拉普拉斯特征值的极限点一定是图的第k + 1 个小的拉普拉斯特征值的极限点，并且给出了图的第k 个大的拉普拉斯特征值的极限 点的最小值和图的第k 个小的拉普拉斯特征值的极限点的下界 笙三兰塑塑垫苎垫堑堑堡堕堕坌塑 3 2 图的拉普拉斯特征值的分布 引理3 1 发h ( g ，) ，- t 2 ( g 1 ) ，z , ，( q ) 和“( g 2 ) ，鸬( g 2 ) ，u ：( g 2 ) 分别是图g l 和 g ，的拉普拉斯特征值，则g ，u g ：的拉普拉斯谱为“、) ，：( g 、) ，a ( g o ， 1 6 ( g 2 ) ，乜( g 2 ) ，以，( g 2 ) 证明l ( g 。u g ：) = d ( g l u g 2 ) 一a ( g u g 2 ) f d ( q ) 01f 爿( g j ) 01 l 0 d ( g 2 ) l 0 爿( g 2 ) j t g d e t u l 一工( g 1u g 2 ) ) = d e t ( p l l ( g f ) ) d e t ( , u i 一上( g 2 ) ) 定理3 1 厶和乓都是递增序列，即 岛丘 三：c q c 乓 证明( 1 ) 设r 0 为图的第个大的拉普拉斯特征值的极限点，则存在图序列 g f 。，使得对f 有“( 6 f ) g a g ，) 且。l i 。r a 。版( q ) 。7 o a ) 若r 1 ，则考虑图序列h 。= g 。u k l j 这里k , l d 是星图th 表示不超过r 的 正整数则 1 1 ：+ 1 ( q ) = 胁( 旺) 以( q ) = 以+ 。( q ) ，i ， 且 ! 受以+ ( 峨) 21 氅肌( 瓯) 2 b ) 若0 r 玉1 ，则考虑图序列见= q u k ：，这里k ：是二阶完全图则 段+ l ( 耳) = 胁( q ) 总( g j ) = 他+ l ( h j ) ，i j 且 l i r a , u 女+ l ( h 。) = l i m y ( q ) = r 因此 r 厶+ 1 从而有k k 。 ( 2 ) 设，丘，则存在图序列q ，使得对f 有“( g j ) 以( q ) 且! i 2 麒( q ，) 2 ， 考虑图序列h ，= 瓯u k ，这里k 。是单点图则 从+ ( h i ) = “( g ) “( g ，) = ，z “h ，) ，i 且 憋，“h 。) - l i r a “( g n ) 2 图的特征根的界 因此 r 乓+ l 从而有“呈。 定理3 2 对任何图序列，有厶，= m 证明n j , j g i j 任何图g ，都有“( g ) = 0 引理3 2 若g 是 阶简单连通图，则 ( 1 ) 2 + 2 c o s 至“( g ) 聆； ( 2 ) 2 - 2 c o s7 r _ i ( g ) hr t 两式左边等号仅当g 兰e 时成立，右边等号仅当g 兰e 时成立 证明见1 15 1 定理3 3 若是厶的最小元，则= 4 证明由引理3 2 ，“( g ) 22 + 2 c o sn ，且等号仅当g 兰p o 时成立，故我们令 瓯兰只，则 “( p ) = 2 + 2 c o sz c i ：2 + 2 c o s 三：, u l ( 只) ，i j l j 月 l i m p , ( p , ) = l i m ( 2 十2 c o sz - - c ) = 4 一一“ ” 因此f 。= 4 定理3 4 若雎是耳的最小元，则对一切k 2 ，都有= 0 证明由引理3 2 ，麒( g ) 2 - 2 c o s 三，且等号仅当g 兰只时成立，故我们令 吒三只，则 “( 鼻) = 2 - 2 c o s 车2 - 2 c o s 三= 从( 只) ，i j 2 j 且 1 i m “( 只) = l i m ( 2 2 c o s - ”) = 0 一 ”。 ” 因此o e 再由定理3 1 可得，对一切k 2 ，都有0 乓又因为l ( g ) 是半正定的，所以对一切 k 2 ，都有= 0 参考文献 参考文献 1 i nl b i g g s ，a l g e b r a i cg r a p ht h e o r y ，( 2 n de d ) ，c o m b r i d g eu n i v e r s i t yp r e s s ， c a m b r i d g e ，1 9 9 3 2 r c b r i g h a ma n dr d d u t t o n ，b o u n d so ng r a p hs p e c t r a ，j c o l n b i n t h e o r ys e r i e sb 3 7 fl9 8 4 ) ，2 2 8 - 2 3 4 3 】d m c v e t k o v i c ，m d o o ba n dh s a c h ，s p e c t r ao f g r a p h s ，t h e o r ya n d a p p l i c a t i o n s ， a c a d e m i cp r e s s ，n e w y o r k ( 1 9 8 0 ) 4 hsw i l lt h ee i g e n v a l u eo f ag r a p ha n di t sc h r o m a t i cn u m b e r ，j l o n d o nm a t h s o e ， 4 2 ( 1 9 6 7 ) 3 3 0 3 3 2 【5 】y h o n g ，a b o u n do nt h es p e c t r a lr a d i u so f g r a p h s ，l i n e a r a l g e b r a a p p l1 0 8 ( 1 9 8 8 ) ， 1 3 5 - 1 3 9 6 d m c v e t k o v i c ，c h r o m a t i cn u m b e ra n dt h es p e c t r u mo fag r a p h ，p u b l i n s t m a t h n o u v e l l es e r , ，1 4 ( 1 9 7 2 ) 2 5 3 8 、 7 aj h o f f m a n ，o ne i g e n v a l u e sa n dc o l o u r i n g so fg r a p h s ，i ng r a p ht h e o r ya n di t s a p p l i c a t i o n s ，( b h a r r i s ，e d i t o r ) ，a c a d e m i cp r e s s ，n e w y o r k ，( 1 9 7 0 ) 8 e a ，n o r d h a n s ，j w g a d d u m ，o nc o m p l e m e n t a r yg r a p h s ，a m e r i c a nm a t h m o n t h l y ， 6 3 ( 1 9 5 6 ) ，1 7 5 1 7 7 ( 9 w n a n d e r s o na n dt d m o r l e y ，e i g e n v a l u e so f t h el a p l a c i a no f ag r a p h rl i n e a ra n d m u l t i l i n e a r a l g e b r a t 1 8 ( 1 9 8 5 ) 1 4 1 1 4 5 1 0 o c a o ，y h o n g ，g r a p h sc h a r a c t e r i z e db yt h es e c o n de i g e n v a l u e ，j g r a p ht h e o r y1 7 ( 1 9 9 3 ) n o 3 ，3 2 5 3 3 1 1 1 d c a o ，a v i n c e ，t h es p e c t r a lr a d i u so f ap l a n a r g r a p h s ，l i n e a r a l g e b r a a p p l 18 7 ( 1 9 9 3 ) ，2 5 1 2 5 7 【1 2 d c a o ，y h o n g ，t h ed i s t r i b u t i o no f e i g m w a l u e so f g r a p h s ，l i n e a r a l g e b r a a p p l 2 1 6 ( 1 9 9 5 ) ，2 1 2 2 4 1 3 d c a o ，b o u n d so ne i g e n v a l u e s a n dc h r o m a t i cn u m b e r ，l i n e a ra l g e b r aa p p l 2 7 0 ( 1 9 9 8 ) ，1 13 【1 4 y h o n g ，o nt h es p e c t r a lo fu n i c y c l eg r a p h ，j o u r n a le a s tc h i n an o r m a lu n i v e r s i t y n a t u r s c i e d 1 ( 1 9 8 6 ) ，3 1 3 4 1 5 向晋捞，图的拉普拉丝特征根的界，硕士论文，华东师范大学，1 9 9 6 望盟笪笙堡塑墨 1 6 y h o n g ，s h a r pl o w e rb o u n d so nt h ee i g e n v a l u e so f t r e e s ，l i n e a ra l g e b r aa p p l1 1 3 ( 1 9 8 9 ) ， 1 0 1 1 0 5 f 1 7 1 l c o l l a t z ，u s i n o g o w i t z ，s p e k t r e ne n d l i c h e r g r a f e n ，a b h m a t h s e r e u n i v h a m b u r g 2 1 ( 1 9 5 7 ) ，6 3 7 1 1 8 】束金龙，洪渊，外平面图和h a l i n 图谱半径的上界，数学年刊，2 l a ( 2 0 0 0 ) ，6 6 7 6 8 2 【l9 】y h o n g ，o nt h el e a s te i g e n v a l u eo fag r a