（应用数学专业论文）图的laplace谱.pdf

abs tract t h e l a p l a c e m a t r i x i s a n a c t i v e a n d i m p o r t a n t s u b j e c t i n a l g e b r a g r a p h t h e o r y . i t i s a d i s c r e t e f o r m o f t h e l a p l a c e o p e r a t o r o n t h e c o m p a c t r i m a n n i a n m a n i f o l d a c t i n g o n t h e g r a p h s . i t h a s b e e n w i d e l y u s e d i n m a n y fi e l d s s u c h a s p h y s i c s 、c h e m i s t r y 、b i o l o g y 、c o m p u t e r n e t s c i e n c e a n d i n f o r m a t i o n t h e o r y , e t c . s o m e r e s u l t s o n t h e l a p l a c e m a t r i x w i l l b e g i v e n i n t h i s t h e s i s : 1 . a p p l y i n g t h e e i g e n v a l u e i n t e r l a c i n g t h e o r e m a n d t h e s k i l l o f e q u i t a b l e p a r t i t i o n o f t h e v e r t e x s e t o f a g r a p h , w e o b t a i n a l o w e r b o u n d o f t h e s e c o n d l a r g e s t l a p l a c e e i g e n v a l u e ) 1 2 ( g ) i n t e r m s o # t h e s e c o n d l a r g e s t d e g r e e d 2 ( g ) o f a g r a p h . m o r e o v e r , t w o n e c e s s a r y c o n d i t i o n s o f a 2 ( g ) = d 2 ( g ) a r e p r o v e d a n d m a n y g r a p h s w h ic h s a t is f y a 2 ( g ) =d 2 ( g ) a r e p r e s e n t e d . 2 . e x t r e m a l g r a p h s w h o s e s u m o f t h e s q u a r e s o f t h e d e g r e e s r e a c h t h e d e c a e n s u p p e r b o u n d a r e d e t e r m i n e d . u s i n g d e c a e n s i n e q u a l i t y , w e o b t a i n a n u p p e r b o u n d o f t h e l a p l a c e e i g e n v a l u e s o n l y i n t e r m s o f t h e n u m b e r s o f v e r t i c e s a n d e d g e s o f a g r a p h . mo r e o v e r , w e p r e s e n t s o m e o t h e r t y p e s o f u p p e r b o u n d s o f t h e l a p l a c e e i g e n v a l u e s o f a g r a p h a p p l y i n g t h e r e s u l t s o n b i p a r t i t i o n w i d t h , w e o b t a i n a l o w e r b o u n d o f t h e l a r g e s t l a p l a c e e i g e n v a l u e i n t e r m s o f t h e n u m b e r s o f v e r t i c e s a n d e d g e s o f a g r a p h . 3 . a n e w p a r a m e t e r o f a g r a p h i s d e fi n e d a n d a r e l a t i o n b e t w e e n t h e n e w p a r a m e t e r a n d t h e t h i r d s m a l l e s t l a p l a c e e i g e n v a l u e o f a g r a p h i s e s t a b l i s h e d . i n a d d i t i o n , w e r e l a t e t h e n e w p a r a m e t e r t o t h e l a r g e s t d e g r e e a n d t h e s e c o n d s m a l le s t d e g r e e o f t h e g r a p h . 4 . a p p l y i n g t h e m e t h o d i n n o n n e g a t i v e m a t r i x t h e o r y a n d t h e r e l a t i o n b e t w e e n t h e l a p l a c e m a t r i x o f a g r a p h g a n d t h e a d j a c e n c y m a t r i x o f t h e l i n e g r a p h o f g , w e g i v e o u t n e w p r o o f s o f t h e k n o w n u p p e r b o u n d s w h i c h w e r e g i v e n勿 me r r i s , l i a n d z h a n g . mo r e o v e r w e c h a r a c t e r i z e e x t r e m a l g r a p h s i n t h e t h e o r e m s o f m e r r i s , l i a n d z h a n g . w e a l s o p r e s e n t a n e w u p p e r b o u n d o f t h e l a p la c e e i g e n v a l u e s o f a g r a p h , a n d c h a r a c t e r i z e e x t r e m a l g r a p h s . l l 第一章引 言 互 1 . 1 基本概念 设g=( v , e ) 是。阶简单图， 其顶点集和边集分别记为 v=v ( g ) = 和1 , v 2 , ， v 和 e二侧引 = e l , e 2 , , e - j . 如果顶点v 是边e : 的一个端 点 ， 则 称。 ， 与e ， 关 联， 与v : 关 联的 边 的 数目 称 为v ; 的 度， 记 作d ( 叼二 d , . 本 文 涉 及 到的图 论 和 矩阵 的 术 语都是 标 准的 ， 可以 见b o n d y 1 0 和b ig g s l l . 称 。 阶 方阵a ( g ) =( d u v ) 为图g的 邻接矩阵， 其中a ( g ) 的行与列表示图g的 顶点，且 当 二 和。 相邻时， 否则. .目，j 11卜u fz!、 一- u u a 易见d u = e % 。 是顶点。 的度.图g的度对角矩阵记为d ( g ) = d i a g d: v e v ( g ) v e v ( g ) ) . 则矩阵l ( g ) = d ( g ) - a ( g ) 称为图g的l a p l a c e 矩阵 对图g 的 每一边e k = v ; , v i ) ， 选择其中 一个顶点为 其正端点， 另 一个为负 端点. 这 一过程称为给图g一个定向. 对图g的一个定向， 其定向 关联矩阵( o r i e n t e d in c id e n c e m a t r ix ) c ( g ) =( e v e ) 如下 : 如蜘 是e 的正端点， 如果u 是。 的负端点， 如果。 和e 不相关联. .一口.j 11110 - 了.j、.、 - 巴 v c 易见l ( g ) =d ( g ) 一 a ( g ) =c ( g ) c ( g ) t ， 其中c ( g ) t 表示c ( g ) 的转置. 图g的l a p l a c e 矩阵以叨与其定向 无关， 且是半正定对称奇异m- 矩阵， 其 每个特征值是非负的， 记作a i ( g ) a 2 ( g ) a n - i ( g ) ? a . ( g ) =0 . 由 图g的l a p la c e 矩阵l ( g ) ， 可以 确 定 列向 量 空间12 ( v ( g ) ) 中 的 一 个二 次型如下: 二 l ( g ) 二 = ( x , l ( g ) x ) 二 ( c t x , c t x ) = 艺( x 。 一 x ) 2 其中。 v 表示顶点u 和v 相邻， 2 0 0 1年 中 国 科 学 技 术 大 学 博 士 学 位 论 文 1 . 2 l a p l a c e 特征值与图的组合性质 1 . 图的复杂度 图的 l a p l a c e 矩阵研究已 有很长的历史，k i r c h h o ff 6 2 在研究电网络时 、 ( 1 8 4 7 年 ) 证明 了 图g 的 生 成 树 数目 等 于 它 的l a p la c e 矩 阵 的 任 何 一 个。 一 1 阶 子式的值 从而将图的生成树的计数间题转化成了纯代数的计算间题. 定理 1 . 2 . 1 . ( 矩阵树定理)n阶图g的复杂度rc ( g ) ( 即其生成树的数 目) 等于其 l a p l a c e 矩阵 l ( g ) 的任何一个 。 一1 阶子式. 特别有 k ( g ) 二 知1 ( g 卜 a_ i ( g ) . 由于有了现代高速计算机的普遍使用，k i r c h h o ff 矩阵树定理为计算图的 生成树数目 提供了 有效的手段. 矩阵 树定理有种种推广， 见【 6 、 1 7 、 1 8 、 5 6 、 6 1 、 6 3 、8 8 等 b i g g s 1 l 用图的子森林的各分支的顶点数的乘积给出了l ( g ) 的特征多项 式的系数， 进一步推广了 矩阵一树定理. 下面用中 表示一个森林， 用p ( 列表 示图0的所有分支的顶点数之积， 特别， 如果fp 是树， 则令p ( 列=i v ( ,d ) i - 定理1 .2 . 2 . 设l ( g ) 的 特征多项式为0 a ( l ( g ) ) =”+ c l a 0 - 1 + + c . - a 则 ( 一 ) 。 二 e p (,b )( 三 : n 一 ， ) ， 其中 和取遍图g的所有边数为 的子森林4p. 对图的l a p l a c e 矩阵展开研究之所以很重要， 最直接的原因是可以用其特 征值来估计图的许多不变量， 如连通度 4 1 一4 4 ) 、 直径( ( 1 9一2 1 ) 、 带宽 ( 5 7 ) 、 二部宽( 3 0一3 2 , 8 4 ) 、 等周数( 7 9 ) 、 最 大割( 3 5 , 7 1 , 7 7 ) 、 超缩 子 和扩充 子( 2一4 ) 、 平均距离( 8 7 ) 、 边前向 指 数( 9 1 ) 等等. 有些图 不变量 的计算是n p - h a r d 的， 而计算图g的l a p l a c e 特征值的计算仅涉及线性方程 组求解8 斗 2 . 图的连通性 定 理 1 .2 . 3 ( f i e d l e r 4 1 ) 设g是n 阶图. 则i n - 1 ( g ) 0 当且仅当g是连 通的. 定理1 . 2 . 4 . ( f ie d le r 4 1 ) 设g 是。 阶 非完全的连通图， d 二 是g的最小度. 则 1 . a 。 一 ， ( g ) -y ( g ) 三t i ( g ) d n , 2 0 0 1年 中 国 科 学 技 术 大 学 博 士 学 位 论 文 2 . a 二 一 ， ( g ) 2 ,7 ( g ) ( 1 一c o s n ) , 其中城 g ) , r l ( g ) 分别为g的点连通度 和边连通度. 从定理1 .2 .3 和定理1 .2 .4 可知， 图g的次小l a p l a c e 特征值与图的连通性 有着深刻的内 在联系， 因此f i e d l e r 4 1 称a 。 一 ， ( g ) 为图g的代数连通度. 3 ， 图的h a m i l t o n 性 众所周知，判定一个给定的图是否含有 h a m i l t o n 圈是一个难间题. 如果 一个图 本身就是h a m i l t o n 图， 那可能还容易一点， 但如果要用图 论的方法证明 一个图不是h a m i l t o n 图， 无疑是困难的， 因为这是一个n p - h a r d 间 题h e u v e l 给出了一个图是 h a m i l t o n图的基于其 l a p l a c e 特征值的必要条件.于是，可 用代数方法断定一些图不是h a m i l t o n 图了( 例如p e t e r s e n 图 ) . 这为研究图的 h a m i l t o n 性提供了 新方法. 定理 1 . 2 . 5 . ( h e u v e l 5 8 ) 设 g是 。阶图. 如果 g有 h a m i l t o n圈， 则对 i =1 , 2 , ， n ， 有 a + ( l ( c . ) ) 入 ( l ( g ) ) 和a , ( k ( 氏) ) a , ( k ( g ) ) , 其中c 表示n 阶圈，k ( g ) 二d ( g ) + a ( g ) . m o h a r 8 1 给出了3 正则图g为h a m i l t o n 图的更为细致的必要条件.其 结果如下: 定理1 .2 . 6 . 设g是。 阶3 正则图. 如果存在下标k 使得或者 i . 当1 k 4 一 2 c o s ( ( 2 7r / n ) k / 2 ， 或 者 2 . 当n / 2 +1 k 。 时，a k 4 一 2 c o s ( 2 7r / n ) ( 5 n + 2 一 2 k ) / 4 1 . 则g不含有h a m i l t o n 圈. 4 . 图的平均距离 图g的平均距离t ( g ) 是图g的一个重要参数. 在计算机通信网 络中有着 广泛的应用. 所谓图g的平均距离是指图g的所有点对之间的距离的平均， 即 p (g ) 二 又 p (v i , v i ) / 其中p ( v i , v j ) 是顶点。 : 和v i 的 距离. 定 理1 .2 .7 . ( m o h a r 7 8 ) 设g 是。 阶 连 通图 ，d l 是它 的 最 大度. 2 人 二 一 ; ( g )+ n - 2 ) 2 : p (g ) :nn - 1 ( f d i +a 。 一 ; ( g ) 4 a 二 一 ; ( g ) ! n ( n 一1 ) 则 十 1 ) z 2 0 0 1年 中 国 科 学 技 术 大 学 博 士 学 位 论 文 定 理1 . 2 .8 . ( r o d r ig u e z 和y e b r a 8 7 ) 设g是有m条边的n 阶 连通图， 且 g有: +1 个不同的l a p l a c e 特征值.则 p ( g ) r 一2 ( : 一1 ) m n ( n 一1 ) 特别，如果 是k 一 正则的，则 p ( g ) r 一k ( ， 一1 ) 几一 1 图g的 所 有 点 对。 ， v , 标， 记作w ( g ) ， 即w ( g ) 二 l a p a la c e 谱决 定 . 即 有 之间的 距离p ( v ; , v 7 ) 之和称为图g的w i e n e r 指 艺p ( v ; , v j ) . m e r r i s 证明了 树的w i e n e : 指标由 它的 . 了 定理1 . 2 .9 . ( m e r r i s 7 0 ) 设t是。 阶树， )1 1 , )1 2 , 特征值，则 a 。 一 ， 是t的非零 l a p la c e w( t ) =艺子 5 . 图的带宽与割宽 设1p 是图g的 顶点集v ( g ) =( v i , v 2 , . - ， 。 ， 到集合 1 , 2 , 射 对实数p , 0 p o o ， 定义p - d i s c r e p a n c y c ( g , 0 ) 如下: a , ( g , 0 ) = m a x 1 0 ( u ) 一 0 ( 二 ) ip ) i i p : 。 ， 。 e ( g ) ) n 上的双 当p 二oc时， a - (g , 0 ) = mu v 酬o u ) 一 c o . 当。 p 0 0 时， o p (g ) :一 兜 n o p (g , p ) , 称为图g的m i n - p - s u m . 当p = 0 0 时，- . ( g ) 就 是图g的重 要参数一 带宽. 带宽在组合优化和现代计算机通信网络研究中 有着重要应用. 众所周知， 带宽 和 m i 。 一 1 - s u 。的计算是 n p - h a r d 的. 图g还 有一个 重要 参数割宽( c u t w i d t h ) ， 记为c ( g ) ， 即c ( g ) = 其中。 ( g , 7g ) 定义如下: 兜 n c ( g , v) ) , c (g , ,p ) 一 冷 慧 “ ” e e (g ) : v , (v ) i v ) (u 川 2 0 0 1年 中 国 科 学 技 术 大 学 博 士 学 位 论 文 其中7p 是图g的 顶点集v ( g ) 二 v 1 , u 2 , . . . , v . 到集 合 1 , 2 , - - , n 上的 双 射. 利用图g的l a p l a c e 特征值估计图的 带宽和割宽等的结果有 定 理1 . 2 . 1 0 . ( j u v a n 和m o h a r 6 0 ) 设g是具 有。条边的。 阶 简 单图 则 a n - 1 ( g ) . 凡- 1 ( g ) n - 1e o f ( g ) 入 ， ( ) n x , ( g ) 1 ; . (n - 1)12: o 1 (g ) : a 1 (g ) nn ( iz 1) ; 3 . o p ( g )p 。 ， 当g=i n 时等式成立. 6 . 图的直径 一个连通图g中 不同顶点之间 所有距离的最大值， 叫 作图g的直径， 记 作d ( g ) . 即 d (g ) 一 、 mv e 跟) p (u , v ) , 其中p ( 二 ， v ) 是顶点。 和v 之间的距离. 不难理解， 直径是计算机通信网络的 有效性和可靠性的一个重要参数.c h u n g 1 9 证明了 关于连通正则图的直径和 模次大根( 模次大的邻接特征 值) 关系的一 个定 理， 该定理说明了次 大根小的 连通正则图具有较小的直径， 即这种图 是有效性能好的通信网 络. 下面是关于 图的l a p l a c e 特征值与直径的一些主要结果. 定理1 . 2 . 1 2 . ( m o h a r 7 8 ) 设是。 阶 连 通图 ，d ( g ) 和d ; 分别 是的的 直 径和最大度，则 n a , - , (g )1: d (g ) : 2 千d i + 当 爵 叫in4 a _ l(g )一 ，” 其中 x 表示不小于x 的最小整数. 2 0 0 1年 中 国 科 学 技 术 大 学 娜 士 学 位 论 文 其中千 x 表示不小于x 的最小整数 定 理1 .2 .1 3 . ( c h u n g ,f a b e r ,m a n t e u ff e l 2 0 和m e r r is 7 2 ) 设g 是。 阶 连 通图 ( g 54 k . ) , d ( g ) 是g的直径， 则 c o s h - ( n一1 ) . _ 浏gl d. 则 1 . ( a n d e r s o n 和m o r l e y 1 ) , ( g ) m a x d+d: u v e e ) , 其中等式成立当且仅当g是二部半正则图; 2 . ( c r o n e 和z i m m e r a n 5 1 ) a i ( g ) d l + 1 ， 其中 等式成立当 且仅当d l = 。 一 1 ; 4 . ( l i 和z h a n g 6 4 于 ) a , (g ) 2 +斌 ( d , + d : 一 2 ) ( d , + d 3 一 2 ) ， 其中 等式 成 立当 且仅当g是正则图、 或星图k 1 ,n - i 、 或3 个点、 或4 个点的路. 2 0 0 1年中 国 科 学 技 术 大 学 仲 士 学 位 论 文 记: =m a x d v + d , : 二。 e ， 设: , y v满足x y e 且d v + d y =r . 另 记 s =m a x d v +d 定理 1 .3 . 3 . : 。 任 e x y . 则有 ( l i 和z h a n g 6 4 ) . 对。 阶图g， 有 a , ( g ) 2 +了( r 一2 ) ( s 一2 ) 设g = ( v , e ) 是。 阶图 ，v中 顶点v 的 度和g中 所有 与。 相邻的 顶点的 度的平均值分别记作d 。 和。 。 ， 则d v m 。 称为v 的 二次度.1 9 9 8 年，m e r r is 利 用二次度概念和关于特征值的g e r 9 g o r i n 圆 盘定理给出了下面的最大l a p l a c e 特征值的上界. 定 理1 . 3 .4 . ( m e r r i s 7 5 ) 设=( v e ) 是n 阶图， 则 l i 和 定理 a , ( g ) m a x d v +二 。 : 。 e v . z h a n g 在肺 5 中改进了定理 1 .3 .4 ， 给出了下面的定理. 1 .3 .5 . ( l i 和z h a n g 6 5 ) 设g 是。 阶图 ， 则 、， _ 、_d d+。力十氏( 成+m ,_ 、 a , ( g) 3 ， 有 a 2 ( g ) d 2 ( g ) , 其 中 当g 是 二 部 完 全 图 或 度 序 列 为蜡 , 2 , 1 ， . . ， 1 ) 的、 阶 树( n 4 ) 时 等 式成立. 定理2 . 3 . 2 . 设g 是。 阶 连通图 ，。 3 , 顶点v ， 和v : 不相邻. 如果 a 2 ( g ) = d 2 , p d i = d 2 且n ( v l ) 二 n ( v 2 ) ， 其 中n ( u ) 表 示 顶点。 的 邻 域 定理 2 . 3 . 3 . 设g是 n阶连通图， n 3 ， 顶点。 l 和。 : 相邻.如果 a 2 =d 2 ， 则( 1 ) v ， 和v 2 没 有公共邻点;( 2 ) d l =d 2 ; ( 3 ) d i + d 2 =。 定理2 . 3 .4 . 设g=k d , # k d , ， 则a 2 ( g ) =d 2 ( g ) = d l . 推论2 . 3 .5 。对于图g ， 如 果k l ,(d ， 一 ; )# k , ,(d ， 一 ， ) c g c k d , ,d , ， 则 a 2 ( g ) =d 2 ( g ) =d l . 推 论2 .3 .6 . 对 于图g 加果k l ,(d 、 一 ， # k , ,(d , 一 ， ) c g c k d # a d t ， 则 a 2 ( g ) = d 2 ( g ) 二d 1 . 2 . 刻划了达到图的度平方和的d e c a e n 上界的极图， 并利用其给出了图的 l a p l a c e 特征值的仅与图的顶点数和边数有关的上界. 利用图的二部宽的已 有结果， 只用图的顶点数和边数给出了最大l a p l a c 。 特征值的一个下界. 定理3 . 1 .4 . 设g是有m条边的。 阶 连通图 则不等式( 1 ) 中的等式 成 立当 且 仅当g 是星图k i ,n - i 或 完 全图k. 定理3 . 1 . 5 . 设g是有m条边的n 阶连通图 则， a l ( g ) 2 m + 1-几 + 骊一? 定 理3 .3 .4 . 设g , l n ( g ) , l , 。和q 同 前 文 定义 . 则有 ( a ) g是欧拉图时， i . m是偶数时， a l(l n (g ) : 2 + 架 i i . m是奇数时， a l ( l - ( g ) ) m( 2 q +2 。一4 ) mz一 1 ( b ) g不是欧拉图时， 1 . m是 偶 数时， ,x 1 ( l n ( g ) ) 2 q . ., 1 尸十乙 一 一刀l7 刀 i i . 二是奇数时， a t ( l n ( g ) ) m( 2 q +2 m一1 ) m2一 1 3 . 分析图g的l a p l a c e 特征向量， 利用图的最大度， 最小度和平均二次度等 给出 几个类型的l a p l a c e 谱半径的上界 定理3 . 2 . 1 . 设g是有。条边的。 阶连通图，d ， 和d o 分别是g的 最大度和最小度. 则 a 1 (g ) : 2 d 1 + 4 二 一 2 d (n 一 1 ) + 2 d 1 (d 、 一 ， )， 其中等式成立当且仅当g是二部正则图. 定理3 . 2 . 2 . 设g是连通图. 则 a , ( g ) d ， 一 、 / d 21 一 。 2 ( g ) . 定理4 . 2 .2 . 设g和叫卿 同定理4 . 2 . 1 . 设d ， 和d_ ， 分别是图g的 最大和次小的度.则 - ( g ) v( 2 d ; 一d 、 一 i 一1 ) ( d 、 一 : +1 ) . 定理4 . 2 . 3 . 设g=( v , 习是。 阶连通图， 则 入 n - z (g ) : wn - 1 ( g ) 5 . 刻划 达到l i 和z h a n g , m e r r is 等给出 的l a p l a c e 特 征值 上界的 极图， 并给出 一个新的上界， 并刻划极图. 利用非负矩阵的 技巧和特征向 量在矩阵 进行 多项式运算时的不变性给出了图的l a p l a c e 特征值其它两个类型的上界， 并刻划了极图. 定理 5 . 1 . 4 . 令 g 当且仅当 g是二部图 二( v e ) 是。 阶连通图. 则 a i ( g ) p ( k ) , 等式成立 定理5 . 2 . 1 .令g=( v , e ) 是。 阶连通图. 对任给顶点。 v . 则 a i ( g ) =m a x d+m u : 。 e v , 当且仅当g是二部正则图和半二部正则图. 记r = m a x d 二 十 d: u v e e l ， 设x , y e v满足x y e e且d . 十 d ， 二: 另记 。 =m a x d u +d u : 。 。 e e x y . 定理5 . 2 .6 . 对n 阶 连通图g， 有 a , ( g ) =2 +了( r 一2 ) ( s 一 2 ) , 当且仅当g是二部正则图或二部半正则图， 或3 个顶点， 或4 个顶点的 路. 定理5 . 2 . 7 . 设g二( v e ) 是有m条边的n 阶 连通图， 则 * 1 ( 卜m a x d ( d , 竺 n u ) + d ( d u + m 业。 。 。 e a 、十 q 2 0 0 1年 中 国 科 学 技 术 大 学 伸 士 学 位 论 文 当且仅当g是二部正则图或二部半正则图 设t = m a x 些 d ,. +m,. ) +d ( d +m, 汉 。 d ,.+ ad ,. + m ,. : 。 。 e e ， 设”e e 满足 d + d = t . 另 记6 = m a x d ,. 探d + - + d : 。 。 e e x y . 定理 5 . 2 .8设g是连通图.则 a , ( g ) 2 +v ( i 一2 ) ( b 一2 ) , 其中等式成立当 且仅当g是二部正则图， 二部半正则图，3 个点的路和4 个点的路. 定理 5 . 3 . 2 . 设g是有。条边的。阶连通图，d ; 和心分别是g的 最大度和最小度.则 入 i ( g ) gd 、 一1 +丫 ( d 、 一1 ) 2 + 8 ( d 了 + 2 m一 ( 。 一 i ) d) 2 其中等式成立当且仅当g是二部正则图. 定理 5 . 3 . 3 . 设g是有m条边的。 阶连通图，d , 和d 、 分别表示图g 的最大和最小度.则 a , ( g ) 三d , +d 、 一i +了 ( d , + d o 一 1 ) 2 +8 ( 2 。一( 。 一1 ) d) 2 其中等式成立当且仅当g是二部正则图. 6 . 给出次小l a p l a c e 特征值a ， 一 ， ( g ) 的一个下 界. 定理5 . 4 . 2 . 设g是。 阶连通图.则 a _ 1 全 m m 1 i 一 d , ， 其中v ( g ) 二 v l , v 2 ， 一、 。 。 ， 且v ; 。 v ( g ) 的 度为d ; = d ( v i ) . 用图 的顶点度来给它的l a p l a c e 特征值定位一直是人们 研究的 重点. 也取得了一些 好的 结果( 5 周 ， 【叫， 7 3 等) . 本章将利用对称实 方阵 的 特征值交 错定理和图的 均匀划分的概念， 给出图g的次大l a p l a c e 特征值的一个依赖于图的次大度 的下界， 并讨论达到下界的极图. 第二节取材于已 发表文章6 6 设: =( x 1 , x 2 , , x n ) 和y 二( y l , y 2 , ， y . ) 是n 维实向 量. 称x 优超、 ， 记 作x y， 加 果对每个k =1 , 2 ， 一 ， 。 ， : 的k 个最大分量之和不小于， 的k 个最大 分量之和， 且x 的所有分量之和与， 的相等.1 9 2 3 年s c h u r 证明， 对。 阶半正定 对 称 方阵h二( h ia ) ， 有( a , , a 2 , ， a n ) 卜 ( h : 工 ， h 2 2 , ， 、 ， ) ， 其中入 1 , a 2 , ， a n 与h i 1 , h 2 2 , . - , h n 。 分别是h的特征值与对角元.由于图g的l a p l a c e 矩阵 l ( g ) 是半正定对称奇异的， 其对角元为d l ( g ) d 2 ( g ) d ( g ) ， 故由 s c h u : 的 这一 结论， 有协 t ( g ) , a 2 ( g ) ， 一 a n ( g ) ) r ( d 1 ( g ) , d 2 ( g ) ， 一， d ( g ) ) . 作 为图g的l a p 工 a c e 矩阵l ( g ) ， 由 于具有其图 论背 景， 自 然 会想到， 上述结论能 否加强?g r o n 。 和m e r r is 认为， 这是可能的.他们证明了下述结论. 定 理2 .1 .1 . ( g r o v e 和m e r r is 5 2 ) 设g=( v ( g ) , e ( g ) ) 是。阶 连 通图 ， 。 2 ， 且设s = u 1 , u 2 , . . . ， 。 ; 是v ( g ) 的子集，1 d 工 ( g ) + 1 , a 工 ( g ) + a 2 ( g ) d l ( g ) + d 2 ( g ) +1 . m e r r i s 7 3 】 进而猜想: 对n 阶连通图g， 有 ( a l ( g ) , a 2 ( g ) ， 二 ， a n ( g ) ) - ( d 工 ( g ) + 1 , d 2 ( g ) , - - - , d( g ) 一 1 ) . g r o v e 4 7 】 证明了m e r r i s 这一猜想成立. 定 理2 . 1 . 2 . ( g r o n e 4 7 ) 设g=( v , e ) 是 连通图， 其顶点集合v=v ( g ) = l v l , v 2 , . . . ， 。 、 不 妨设g的 度序 列为d l d 2 d， 其中d ; =d ( v i ) . 则对 每个整 数k =1 , 2 , - - - ， 。 一 1 ， 有 无k 又“ : : 艺 d ; + t k , 2 0 0 1年 中 国 科 学 技 术 大 学 博 士 学 位 论 文 其中t * 表示顶点。 1 , v 2 , . . . ， : * 在g中的导出 子图的 连通分支数. 一个有趣的问 题是， 对。 阶 连 通图g ， 由 于入 1 ( g ) 十 入 2 ( g ) _ d l ( g ) + d 2 ( g ) + 工 ， 而a l ( g ) d , ( g ) +1 ， 是否有a 2 ( g ) ? d 2 ( g ) ? 利用对称实 方阵及其主子矩阵的 特征值之间的 交错定理， 以 及m o h a r 侧关于图g的均匀分拆与其l a p l a c e 特 征值的联系的一个重要结论，我们肯定了这个想法. 2 . 2 次 大l a p l a c e 特 征 值的 下 界 先 介绍图 的 顶 点 集的 均匀 划 分( e q u i t a b l e p a r t i t i o 司的 概念 设g=( v习是。 阶连通图， 且v , v 2 , ， v k 是其顶点集 称v i , v 2 ， 二， v k 是v的均匀划分当且仅当对每一对 ， ， 二1 , 2 , v一个划分. . , k ， 存 在常数 标的 二v d ,j , 使 得 从 v , 中 的 每 - ta 点 ” ， 恰 有 d ij a 边 连 接 到 v i 中 ， 即 有 。凰 a . ,e v 其中a=( 刃是g的 邻接矩阵. 定 理2 .2 . 1 . ( m o h a r 7 9 ) 设g=( v , e ) 是连 通图 ，v 1 , v 2 一 个 均匀 划 分， 其 参 数为d ij , i a n ( 哟. 对正整数r , 1 r n , 设a , 是a的r 阶主子矩 阵，1 r n . 则对每一个工 ix 2 卜 x 2 ， 和y 卜 ， . 定义图w=( v ( w) , e ( w) ) 如 下: 顶点集v ( w ) = x , u x 2 u y u v 1 , v 2 ， 和e ( w ) = v , u lu e x l u y ) u v 2 u iu x 2 u y u v , v 2 . ( 见图1 . ) 易 见， 图w的 最大 度d , ( w ) 和次 大 度d 2 ( w ) 满 足d l ( w ) =i + : ; + ， i + 二 : + 。 = d 2 ( w ) . 关于图w的次 大l a p l a c e 特征值 a 2 ( w) ， 有 引理 2 . 2 . 4 . a 2 ( w) d 2 ( w) . 证明如果二 ， 二x : 二二 ， 则d , ( w) = d 2 ( w) . 图w的顶点集v ( w) 具有均 匀划分: v i = v 1 b v 2 =i v 2 , v 3 =y , v 4 =x , 和v s 二x 2 . 于是定理2 . 2 . 1 中 所定义的矩阵b=( b ;, ) 为: 、1了 八曰刃nun们1土 一 一 1 一 y 一 x d , 一 y 0 一1 2 0 0 0 1 一1 0 0 dl月-1-l0 了一、 -一 b 其中d : 二d , (