（系统分析与集成专业论文）图的拉普拉斯特征值与全控制参数.pdf

2 0 0 7 年上海大学硕士学位论文 摘要 在近四十年里，随着计算机科学的迅速发展，图论的发展也非常迅猛，其中图 的控制数理论是图论中发展最快的几个领域之一控制数理论能够快速发展的主 要原因是它在组合优化、编码理论、计算机科学、通信网络、监视系统和社会网络 等理论与实践中有着重要的应用随着研究的深入和应用的激发，各种新的控制 参数不断涌现其中图的函数( 全) 控制数就是( 全) 控制数的一类自然推广由于 函数的引入，致使利用函数性质来研究控制数成为可能目前，函数控制数已成为 图的控制理论中一个崭新而富有挑战的研究方向 在图论中，为了研究图的性质，人们引进了图的邻接矩阵，关联矩阵，距离矩 阵，拉普拉斯矩阵等各种矩阵代数图论的个主要问题就是研究图的性质能否 以及如何由这些矩阵的代数性质反映出来而各种矩阵中，很重要的就是图的拉 普拉斯矩阵因为拉普拉斯矩阵的特征值与图的很多不变量有着密切的联系正 如m o h a r 【1 1 所说t 图的拉普拉斯矩阵的特征值更能反映它的图论性质所以，对 图的拉普拉斯矩阵的特征值的研究也越来越受到人们的广泛关注 本文主要研究了全控制数和符号全控制数的n - g 型不等式，以及图上几类全 控制参数与拉普拉斯特征值的关系，其相应的结果分为以下两个部分t 第一部分，我们研究了图上符号全控制数w 的n o r d h a u s - g a d d u m 型不等 式，给出了路与其补图的符号全控制数和的上界，以及图与其补图的符号全控制 数和的下界( 有关结果被运筹学学报录用) 第二部分，我们给出了连通图上代数连通度o ( g ) 关于全控制数m ( g ) 的两个 上界，并对第二个上界给出了达到此上界的图的刻画给出了代数连通度关于符 号全控制数w 饵) 以及符号控制数( g ) 的上界，并证明了界是紧的( 有关结果已 投c z e c h o s l o v a km a t h e m a t i c a lj o u r n a l 杂志) 最后给出了任意图上和正则图 上拉普拉斯谱半径a ( g ) 关于符号控制数的下界，并给出了刻画，另外对拉普拉斯 谱半径关于符号全控制数的下界进行了讨论 关键词：路；补图；全控制数；符号全控制数；符号控制数；拉普拉斯矩阵； 代数连通度；拉普拉斯谱半径；界；n o r d h a u s - g a d d u m 型结果 2 0 0 7 年上海大学硕士学位论文 i i i ii i _ - _ _ _ _ _ _ - _ _ i e j = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = i l l i _ = j = = = = = j = a _ i ，= l i e = = l a b s t r a c t w i t h i nt h el a s tm o r et h a nt h i r t yy e a r s ，c o n c u r r e n tw i t ht h eg r o w t ho fc o m - p u r e rs c i e n c e ，g r a p ht h e o r yh a s8 e e l le x p l o s i v eg r o w t h t h es t u d y o fd o m i n a t i o ni n g r a p h si so n eo ft h ef a s t e s tg r o w i n ga r e a sw i t h i ng r a p ht h e o r y t h er a p i dg r o w t h o f d o m i n a t i o nr e s e a r c hi sa t t r i b u t a b l em a i n l yt oi t ss om a n ya p p l i c a t i o n st oo t h e rs c i - e n 懈a n dr e a lw o r l dp r o b l e m s s u c h8 , 8c o m b i n a t o r i a lo p t i m i z a t i o n ，c o d i n gt h e o r y , 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 s ，m o n i t o rs y s t e ma n ds o c i a ln e t w o r k t h e o r y w i t hr e s e a r c h i n gd e e p l y , m a n yd i f f e r e n tt y p e so fd o m i n a t i o np a r a m e t e r s h a v es p r u n gu pr a p i d l y ( t o t a l ) d o m i n a t i n gf u n c t i o ni ng r a p h si st h en a t u r a lv a r i - a t i o no f ( t o t a l ) d o m i n a t i o n t h u s ，i ti sp o s s i b l et os t u d yd o m i n a t i o ni nt e r m so f f u n c t i o n a lp r o p e r t i e s n o w a d a y s ，t h es t u d yo nd o m i n a t i n gf u n c t i o n si sa f l e wa n d c h a l l e n g a b l er e s e a r c hf i e l di nd o m i n a t i o nt h e o r e y t h e r ea r ev a r i o u sm a t r i c e st h a t9 1 en a t u r a l l ya s s o c i a t e dw i t hag r a p h s u c ha 8 t h ea d j a c e n c ym a t r i x ，t h ei n c i d e n c em a t r i x ，t h ed i s t a n c em a t r i xa n dt h el a p l a c i a n m a t r i x o n eo ft h em a i np r o b l e m so fa l g e b r a i cg r a p ht h e o r yi st od e t e r m i n ep r e - c i s e l yh o w ，o rw h e t h e r ，p r o p e r t i e so fg r a p h sa r er e f l e c t e di nt h ea l g e b r a i np r o p e r t i e s ( e s p e c i a l l ye i g e n v a l u e s ) o fs u c hm a t r i c e s a m o n gt h ea b o v em e n t i o n e dm a t r i c e so f g r a p h s ，t h em o r ei m p o r t a n to n e i st h el a p l a c i a nm a t r i xo fg r a p h s s i n c et h ee i g e n * v a l u e so ft h el a p l a c i a nm a t r i xh a v eac l o s er e l a t i o nt on u m e r o u sg r a p hi n v a r i a n t s ， i ti sj u e ta sm o h a r i 】s a i tt h a t ：t h e ya r em o r en a t u r a la n dm o r ei m p o r t a n tt h a nt h e e i g e n v a l u e so ft h ea d j a c e n c ym a t r i x s o ，m o r ea n dm o r ea t t e n t i o nh a sb e e np a i d o nt h el a p l a c i a ne i g e n v a l u e s i nt h i sp a p e r w em a i u l yi n v e s t i g a t en gt y p er e s u l t sf o rt o t a ld o m i n a - t i o nn u m b e ra n ds i g n e dt o t a ld o m i n a t i o nn u m b e r ，t h er e l a t i o n s h i pb e t w e e ns o m e k i n d so ft o t a ld o m i n a t i n gf u n c t i o n sa n dl a p l a c i a ne i g e n v a l u e si n 擎a p h 8 ，a n dt h e c o r r e s p o n d i n gr e s u l t sa r et h ef o l l o w i n gt w op a r t s ： i nt h ef i r s tp a r t ( c h a p t e r3 ) ，w es t u d yn o r d h a t m - g a d d u mt y p er e s u l t sf o rs i g n e d t o t a ld o m i n a t i o nn u m b e r 啊a nu p p e rb o u n do nw ( r ) 十w ( - 夏) f o rap a t hr 2 0 0 7 年上海大学硕士学位论文i i i a n dal o w e rb o u n do i lw ( g ) + w ( _ ) a r ep r e 触n t e d i nt h es e c o n dp a r t ( c h a p t e r4 ) ，w ep r e s e n tu p p e rb o u n d so na l g e b r a i cc o n l l e c - t i v i t yq ( g ) o fac o n n e c t e dg r a p hgi n v o l v i n gi nt h et o t a ld o m i n a t i o na n ds i g n e d t o t a ld o m i n a t i o nn u m b e r s a n dw ep r e s e n tl o w e rb o u n d so nl a p l a c i a ns p e c t r a l r a d i u sa ( g ) o fac o n n e c t e dg r a p hi n v o l v i n gi nt h es i g n e dd o m i n a t i o nn u m b e r s k e yw o r d s ：p a t h ；c o m p l e m e n t ；t o t a ld o m i n a t i o nn u m b e r ；s i g n e dt o t a l d o m i n a t i o nn u m b e r ；s i g n e dd o m i n a t i o nn u m b e r ；l a p l a c i a nm a t r i x ；a l g e b r a i cc o n - n e c t i v i t y ；l a p l a c i a ns p e c t r a lr a d i u s ；b o u n d ；n o r d h a u s - g a d d u mr e s u l t 原创性声明 本人声明，所呈交的论文是本人在导师的指导下进行的研究工作除了文中特 别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果， 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示了谢意 签名； 史 扣 日期；上川年b 月，日 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，h p , 学校有权保留论 文及送交论文复印件；允许论文被查阅和借阅；学校可以公布论文的全部或部分 内容 保密的论文在解密后应遵守此规定 貅坼导师签名隽 墨 日期t 1 年6 月f 1 日 j 2 0 0 7 年上海大学硕士学位论文 1 第一章引言 本章主要介绍图的控制数理论的产生背景，应用领域及其主要研究方 向，以及图的拉普拉斯特征根的研究背景和进展，最后指出了本文所做的 主要工作 1 1 图的控制数理论的产生背景和主要研究方向 在过去的三十多年里，随着计算机科学的迅速发展。图论也得到了飞速发展， 而图论中发展最快的领域也许就是控制数理论的研究控制数理论能够快速发展 的主要原因是它在组合优化、编码理论，计算机科学、通信网络，监视系统和社会 网络等理论与实践中有着重要的应用背景 对图的控制数的研究可以追溯到十九世纪中期，当时人们注意到这样的问题t 个国际象棋棋盘上，最少放置几个皇后就可控制( 攻击) 或占据所有的方格? 这 可以看作图的控制数问题的最早形式在1 9 6 0 年前后，人们开始对图的控制数进行 数学理论方面的研究，起初还是集中于研究仃扎棋盘的各类控制所公认的图的 控制数理论是在1 9 5 8 年由b e r g e 和1 9 6 2 年由o r e 共同建立的1 9 5 8 年，b e r g e 在 图论专著中首次定义。控制数”这一概念( 虽然当时他用了另外的名称) 1 9 6 2 年， o r e 在图论著作中，正式定义并使用沿用至今的控制数术语“d o m i n a t i n gs e t 。和 。d o m i n a t i o nn u m b e r 。1 9 7 7 年，c o c k a y n e 和h e d e t n i e m i 在一篇报告中综述了 当时已知的有关图的控制数的结果，并且开始使用符号，y 表示图的控制数，此符号 直沿用至今此后的1 0 多年里，这理论开始引起人们的广泛关注并得到迅速发 展，众多的研究者纷纷投入到控制数同题的研究中来，控制数研究的文献也频频出 现在各类数学期刊上据1 9 9 0 年鬈d i s c r e t em a t h e m a t i c s 出版的一期专辑( v o l 8 6 ) 统计，截至当时累计的文献就达到了4 0 0 篇随后控制数理论成为图论中个 重要的研究热点鉴于此理论的迅速发展，1 9 9 8 年，美国学者h a y n e s ，h e d e t n i e m i 和s l a t e r 7 8 ，切在对此领域进行系统总结后。首次出版了两本关于图的控制数 理论的专著鬈d o m i n a t i o ni ng r a p h s - - a d v a n c e dt o p i c s 和鬈f t m d a m e n t a l so f d o m i n a t i o ni ng r a p h s ，其中在f h n d a m e n t a l so fd o m i n a t i o ni ng r a p h s 中 2 0 0 7 年上海大学硕士学位论文 2 引用了1 2 0 0 多个文献这两本专著的出版，为人们深入研究这理论奠定了坚实 的基础，同时也巩固了控制数理论在图论中的地位自1 9 9 8 年以来，图的控制数理 论得到了前所未有的发展2 0 0 0 年，a m s 为d o m i n a t i n gs e t s ，i n d e p e n d e n ts e t s ， d i q u e s 在分类条目中专列了一项0 5 g 6 9 关于控制参数理论研究的全面进展可参 阅【7 8 ，7 9 】 图的控制数理论已成为图论的一个重要研究领域，而其之所以如此迅速地发 展起来主要是基于以下三个方面的因素，( ) 它在现实世界和诸如。覆盖。监 控”等数学模型中都可以归结为图的控制问题例如，一个通讯网络可以看作一个 图，而网络节点与通讯线路就是图的顶点和边在某些网络节点上放置监控设备来 监控整个网络的运行状况，而为了降低成本，总希望在监控整个网络的情况下。 可以选择尽可能少的节点来放置监控设备如何选择这些节点就是寻找图的最小 控制集的问题( - - ) 控制参数的定义类型具有多样性根据实际背景的不同，现 已定义的控制参数有几十种之多，而且随着研究的深入和应用背景的不断扩大。 新的参数仍在不断涌现( 三) 图的控制参数判定问题的n 蹦e 全性与其他组合优 化中n p - 完全问题有着紧密而自然的关系在特殊图类( 如树，弦图，区间图，置 换图，a t - b e e 图等) 上，研究各类控制参数的计算复杂性已成为组合优化领域中 个引人入胜而富有挑战性的研究方向 随着控制数理论研究的深入和应用领域的拓宽，各种控制参数也不断涌现 到目前为止，控制参数种类已经多达几十种，其中，函数( 全) 控制数就是( 全) 控 制数的一类自然推广1 9 9 6 年，b a n g e 埘l 等引入了一类推广的图的控制数一弘 控制函数设p 是一实数集，函数，：v ( c ) 一p 称为图g 的弘控制函数，如 果对每个点口y ( g ) ，有( n n ) 1 ，这里，m = ul 删e ( g ) u t ， ，( m ) = 乏乙。m ，( t ) 图的弘控制数定义为， 伽= m i n ( f ( v ) i ，是g 的p 一控制函数 当p = 1 0 ，1 时则是图的标准控制数；当p = - 1 ，1 ) 和p = - 1 ，0 ，1 ) 时，则分 别是图的符号控制数和负控制数，其相关研究结果可参见文献阻，3 6 ，3 7 ，4 7 ，4 8 ， 4 9 ，5 0 ，5 3 ，6 6 ，8 2 】把上述定义中的，( m ) 1 改为，( ( ) ) l 就得到相应的 全控制数、符号全控制数和负全控制数它们的定义具体见本文第二章 1 9 5 6 年，对图与其补图色数的积与和，n o r d h a u s 和g a d d u m1 14 l 两人建立了两 2 0 0 7 年上海大学硕士学位论文3 个著名不等式，以后，这种寻找图与其补图的各种参数的和或者积的界，成为观察图 上各种参数性质的个非常有意义的形式，他们被称为n o r d h a u s - g a d d u m 型不等 式1 9 7 2 年，j a e g e r 和p a y a nl z 4 1 建立了第个涉及控制数的n o r d h a u s - g a d d u m 型不等式最近，r h a a s 和t b w e x b e r f f i l 获得了符号控制数的n o r d h a t m - g a d d u m 型不等式几个和控制参数有关的n o r d h a u s - g a d d u m 型结果，我们会在 第二章有所介绍 目前，对于函数控制参数的研究主要集中在以下几个方面； ( 1 ) 确定各种控制参数的上下界，在一些特殊图上计算它们的值； ( 2 ) 寻找各种控制参数之间的关系，以及控制参数与图的其他参数的关系研 究； ( 3 ) 给出极端图类的结构性质的刻画； ( 4 ) 讨论各种控制参数的复杂性问题，算法及应用问题 1 2 图的拉普拉斯特征根的研究背景及进展 人们对拉普拉斯矩阵的研究，可以追溯到1 6 0 多年以前拉普拉斯矩阵最著 名的应用是在1 8 4 7 年k i r c h h o f f 研究电流理论时所发现的矩阵一树定理中t 设g 是一个有，1 个顶点的连通图且l ( g ) 是它的拉普拉斯矩阵，去掉以g ) 的第i 行及 j 列得到一个n 一1 阶的子矩阵，记为l ( iij ) 则l ( iij ) 的行列式的绝对值等于 图g 的生成树的个数因此，图的拉普拉斯矩阵有时被称为k i r c h h o f f 矩阵又 因为拉普拉斯矩阵在人们研究电路网路时有着重要应用，该矩阵也被称为容许矩 阵在数学物理上，由于拉普拉斯矩阵可以被视为拉普拉斯微分算子的离散情形 【l 】，故在数学上，该矩阵一般被称为拉普拉斯矩阵图的拉普拉斯矩阵的特征值被 称为图的拉普拉斯特征值 图谱理论主要研究图的邻接矩阵和拉普拉斯矩阵的特征值和特征向量，是图 论研究的一个重要方向对图的邻接矩阵的特征值的研究，目前已形成比较成熟 的理论，详见专著( 1 1 ，1 2 ，6 0 j 与图的邻接矩阵的特征值相比，由于拉普拉斯矩阵 的特征值与图的结构之间有着更自然的联系，更能反映图的图论性质叽因此对 拉普拉斯矩阵的特征值的研究正越来越引起人们的关注，是当前图论研究中的一 2 0 0 7 年上海大学硕士学位论文 4 个热点问题 对图的拉普拉斯特征值的研究不仅具有重要的理论价值。而且还有广泛的应 用背景 1 1 例如，在物理和化学的很多问题中，拉普拉斯特征值起到中心的作用 ( 见1 3 ，4 ，5 ，6 ，7 】) 拉普拉斯特征值也可以被用来给出图的几何表示( 见【2 8 】p 2 8 4 ) ， 而这与圈论中近来最重要的进展之一一图的c o l i nd ev e r d i & e 数有着密切的关 系瞄，同时也在物理，理论化学、计算机科学、电子工程中均有重要的应用因 此，拉普拉斯特征值不仅引起了数学家的关注，而且也引起了不少物理学家和化 学家的重视 目前研究拉普拉斯特征根的方法主要有三种t ( 1 ) 代数方法t 即用矩阵论并结合图的图论性质来研究拉普拉斯特征值，如文 献f 6 9 1 ； ( 2 ) 几何方法，即研究图的拉普拉斯矩阵l ( g ) = 9 ( a ) 一a ( a ) 所对应的二次 型并结合图的图论性质来研究拉普拉斯特征值，如文献【2 5 1 ； ( 3 ) 概率方法t 即通过引入随机路的概念，利用概率论的方法研究拉普拉斯特 征值，如文献【2 6 】 另外，也可以借助于计算机来对拉普拉斯特征值进行研究，如文献 8 0 】在本 文中，我们主要利用代数方法来对拉普拉斯特征值进行研究 在图的拉普拉斯特征值中，最重要的有两个- 图的最大拉普拉斯特征值( 即拉 普拉斯谱半径) 和图的第- - d , 的拉普拉斯特征值( 即代数连通度) 目前，利用代数 方法和几何方法对拉普拉斯特征值的研究主要集中在以下几个方面。 ( 1 ) 对拉普拉斯谱半径的研究； ( 2 ) 对代数连通度及其所对应的特征向量的研究； ( 3 ) 对拉普拉斯特征值与图的不变量之间的关系的研究，如与图的连通度的关 系； ( 4 ) 对图的其他拉普拉斯特征值的研究 1 3 本文的主要工作 本文主要研究了全控制数和符号全控制数，以及两类函数全控制数与拉普拉 2 0 0 7 年上海大学硕士学位论文 5 斯特征值的关系，本文的主要结构如下， 第一章引言部分主要介绍图的控制数理论及图的拉普拉斯特征值的产生背景 和进展； 第二章给出图论中常用的基本概念和记号，以及常用控制集和拉普拉斯特征 值的概念； 第三章首先给出符号全控制数的n o r d h a t m - g u d d u m 型不等式，给出了路与其 补图的符号全控制数和的上界，然后给出图与其补图的符号全控制数和的下界； 第四章首先给出连通图上代数连通度关于全控制数的两个上界，并对第二个 上界给出了达到上界的图的刻画然后也给出了代数连通度关于符号全控制数以 及符号控制数的上界，并都证明了界是紧的最后给出了任意图上和正则图上拉 普拉斯谱半径关于符号控制数的下界，并给出了刻画，另外对拉普拉斯谱半径关 于符号全控制数的下界进行了讨论 2 0 0 7 年上海大学硕士学位论文 6 第二章基本符号和结论 2 1 基本概念和记号 本文所讨论的图均是无孤立点，无环无多重边的有限简单图凡是文中未加定 义的术语和符号，可参看文献【2 2 ，3 3 ，7 8 】为了叙述方便，我们首先引入一些定义 和记号设g = ( ke ) 是简单图，y ( g ) ，e ( a ) 分别表示图g 的顶点集和边集， g 中点的数目n = i y ( g ) i 称为图g 的阶数如果图日满足条件v ( h ) v ( a ) 和e ( h ) e ( g ) ，则称日为图g 的个子图对s y ( g ) ，用g 旧表示由s 导 出的子图 图g 中点z 的开邻域定义为a ( z ) = 妇ix y e ( g ) ) ，z 的闭邻域 为g m = b ( z ) u z ) 更一般地，对任意的x y ( g ) ，我们定义g o ( x ) = 也x n o ( z ) ，n o x = n o ( x ) ux 在不引起混淆的情况下，上述符号可分别简记 为( z ) ，陋】，n ( x ) 和n i x 我们称d ) = i ( z ) l 为点茹的度数，度数为1 和0 的点分别被称为图的悬挂点和孤立点分别用j ( g ) 和a ( c ) 表示图g 的 最小度和最大度图g 中度为奇数和偶数的点分别称为奇度点和偶度点所 有顶点的度都等于k 的图g 称为肛正则图在图g 中如果两个不同的顶点在g 中是不邻接的，则称它们是独立的如果点集s v ( a ) 中所有点都是相互独立 的，则称s 是g 的独立集 由n 个顶点构成的路和圈一般记作昂和g 若图g 中的任意两个相异 点之间都有边相连，则称g 为完全图，n 个顶点的完全图记作j 矗用g = ( ，k ，v k ；e ) 表示顶点集是l 惶1 k ，边集是 z 掣e ( g ) lz k ，y y j ，1 t 0 ，至少存在一个点 2 0 0 7 年上海大学硕士学位论文 8 “( t ，) ，使得f ( n m ) 1 ，2 ) 类似地，定义图的符号控制数和上符号控制 数，为。 r ( g ) = m i n w ( f ) l ，是g 的符号控制函数) 和 r ( g ) = m a z w ( ) j ，是g 的极小符号控制函数) 2 0 0 1 年，z e l i n l m 2 引入图的符号金控制数( s i g n e dt o t a ld o m i n a t i o n ) 的概念 函数，：v ( a ) 一 - 1 ，1 ) 称为g 的符号全控制函数，如果对任意点t ，v ，有 i v 】1 个符号全控制函数，是极小的当且仅当对每一个点t ，k ( v ) 0 ， 至少存在一个点t ( t ，) ，使得，m l ，2 类似地，定义图的符号全控制数 和上符号全控制数，为： w ( g ) = m i n 叫( ，) l ，是g 的符号全控制函数) 和 e ( g ) = m a x w ( f ) l ，是g 的极小符号全控制函数 最近，x i n g ：s o l 等人引入了缸符号全控制数( 缸s i g n e dt o t a ld o m i n a t i o n ) 设k 为 正整数。1 七f y | 函数，：y ( q 一 一1 ，1 称为g 的缸符号全控制函 数( k s t f ) ，如果y 中至少存在k 个点，满足i v 】1 一个k s t f ，是极小的， 如果对每个点 v ，不存在g 的一个k s t fg ，使得g ，且g ( v ) ，( 口) 图的 缸符号全控制数和肛上符号全控制数分别为- 。( g ) = m i n w ( f ) i ，是g 的k s t f 和 r 2 。( g ) = m i n w ( f ) i ，是g 的极小k s t f 显然当k = j v i 时，。( 回为符号全控制数，而砭。( g ) 就是上符号全控制数 近些年来对上述各种函数控制参数的研究主要集中在界、判定问题的复杂性、 算法、各种参数之间的关系以及极图的刻画等方面下面我们给出相关的主要研 究结果 关于( 上) 全控制数方面的研究主要有以下结果， 2 0 0 7 年上海大学硕士学位论文 9 定理2 2 1 ( 【2 1 】) 若g 是n 阶n 3 连通图，则m ( g ) s2 n 3 ，且此界是可达 的 定理2 2 2 ( 5 4 1 ) 若g 为n 阶连通图，最小度6 ( c ) 2 ，且g 隹 c 3 ，g ，g ，c l o ， 则仉( g ) 4 n 7 定理2 2 3 ( 6 2 】) 设n 阶图g ，最小度6 ( c ) 3 ，则m ( g ) 7 n 1 3 下一个定理是文献【6 2 】中的猜想，2 0 0 4 年分别被a r c h d e a c o n 等八位研究者 独立地解决了 定理2 2 4 ( 1 0 】) 设礼阶图g ，最小度6 ( c ) 3 ，则m ( g ) 2 ，且此界是可达 的 最近，t h o m a s s e 和y e o 又得到了关于全控制数的一个新上界 定理2 2 5 ( 7 5 】) 设n 阶图g ，最小度6 ( g ) 4 ，则m ( g ) 3 n 7 其他有关全控制数的研究成果可参阅文献 5 6 ，5 7 ，6 5 j 定理2 2 6 ( e 3 1 ) 若g 为他阶的连通无爪图，最小度为6 ( g ) ，则 蹦郎雕誊x ， 此外，r ( g ) = 2 + z ) 3 当且仅当g 吼u 吼j 若6 3 ，4 ，5 ) ，则r t ( g ) = 4 ( 6 + 3 ) 当且仅当g 仍或6 = 5 时g ，i 若6 6 ，则n ( g ) = 2 当且仅 当g ， 吼u 岛，绣和，的构造见文献【6 3 】 关于c 七) 符号控制数的研究，给出下面主要结果， 定理2 2 7 ( 【6 6 】) 设g 为简单图且l y ( g ) i 3 ，a ( g ) 3 ，则( g ) n ，且此 界是可达的 2 0 0 7 年上海大学硕士学位论文 1 0 定理2 2 8 ( 【6 6 】) 设g 为简单图，如表示g 的2 度点的个数若( g ) 5 ， d 2 = 0 ，则( g ) n 5 ，且此界是可达的 定理2 2 9 ( 【5 8 】) 设g 是n 阶庇- 正则图，j l 懈，慷：麓 且界都是可达的 定理2 2 1 0 ( 【8 8 】) 设g 为n 阶图，则 ( g ) 2 1 + 定理2 2 1 1 ( 【8 8 】) 设g 为凡阶图，则 ( g ) 再5 + 西2 - - 五a 竹 一n 2 0 0 0 年，k a n g 和s h a l l 得到任意图符号控制数的一个下界 定理2 2 1 2 ( 【5 0 】) 设t 为n 阶树，则( t ) 翌2 乒，其中z 为t 的奇点个数 且界都是可达的 定理2 2 1 3 ( 【5 0 】) 对任意图g 一( n ，m ) ，7 0 ( t ) m a x n 一 ，n 一堑铲) 最近，s o h n 等人改进了定理2 2 1 2 和定理2 2 1 3 ，得到下面结果t 定理2 2 1 4 ( 【5 9 】) 设g 为n 阶任意图，n o 为g 的奇点个数，则 们) 譬等 定理2 2 1 5 ( 【5 9 】) 设g 为立方图，且它的每个点至少包含在一个三角形中，则 ( 刁2 n 3 定理2 2 1 6 ( e 6 7 ) 每一个不同于p e t e r s e n 图的连通立方图g ，满足( t ) n 一 2 f 鼽4 2 0 0 7 年上海大学硕士学位论文 1 1 定理2 2 1 7 ( 【5 3 】) 设g 为n 阶七- 正则图，则 且界都是可达的 蹦g ， 学k 2 + 4 k + 1 ，：麓 若图g 的每个点的度数均为k 或k 一1 ，则称g 为几乎七一正则图2 0 0 1 年，w a n g 和m a o 得到几乎正则图的符号控制数的上界 定理2 2 1 8 ( 【9 】) 设g 为n 阶几乎七+ 1 正则图，则 且界都是可达的 一 麓k + 5 k + 2 ，：麓 关于( 上) 符号全控制数的研究，给出下面主要结果。 定理2 2 1 9 ( 【2 】) 若g 为礼阶岛正则图，则 w c g ， 妻，：耋主羹： 且此界是可达的 定理2 2 2 0 ( 5 5 】) 若g 为n 阶图，则w ( g ) 4 v 互- n - + 1 + 1 一m 等式成立当且 仅当g 7 了是一类图的集合，它的具体构造可参阅文献【5 5 】 定理2 2 2 1 ( 5 5 】) 若g 为n 阶图，最小度6 2 ，最大度为，则 且此界是可达的 馋，( 黔粥蒜黑) 2 0 0 7 年上海大学硕士学位论文 1 2 定理2 2 2 2 ( 5 5 】) 若g 为f l 阶图，边数为m ，则w ( g ) 2 ( n m ) 定理2 2 2 3 ( 【5 5 】) 若t 为仃2 阶的树，l ( t ) 为所有叶子的集合，则w ( t ) 2 ， 等式成立当且仅当每个点t ，( y ( 一工( t ) ) 是奇度点且至少与( d ( v ) 一1 ) 2 个 叶子邻接 定理2 2 2 4 ( 【5 5 】) 若g 为n 阶七- 正则图，则 职g ， , 蠡k + 2 k - 1 瓢麓 且此界是可达的 此外，文献【1 6 】中也给出了几乎正则图上u ( g ) 的上界 关于控制参数n o r d h a u s - g a d d u m 型结果的研究，给出下面主要结果。 定理2 2 2 5 ( 2 4 】) 设g 为n 2 阶图，则 ，y ( g ) + ，y ( 召) 1 + 1 定理2 2 2 6 ( 【2 3 】) 设g 为n 阶图，控制数为，y ( g ) ，满足，y ( 召) 5 则双控制数 讹( g ) 有n o r d h a u s g a d d u m 型结果； y 2 ( g ) + 一y j ( 召) n 一( g ) + 6 ( g ) 一1 h a r a r y 和h a y n e s 在文献【2 3 】中还提出猜想，2 0 0 4 年分别被e f s h a h 等三 位学者解决，并加强了猜想结果 定理2 2 2 7 ( 1 5 】) 设g 为7 , 阶图，整数k 1 ，若图g 控制数，y ( g ) ，满足 ，y ) k + 2 ，则 饥( g ) + 讯( 劢7 , 一a ( g ) + 5 ( g ) 一1 定理2 2 2 8 ( 1 5 1 ) 设g 为n 阶图，控制数，y ( g ) 满足，y ( 召) 3 ，则 m ( g ) + m n a ( g ) + 5 ( g ) 一1 2 0 0 7 年上海大学硕士学位论文 1 3 定理2 2 2 9 ( 【7 1 】) 设g 为n 阶图，则( g ) + ( 召) = 2 n 且( g ) ( 劢= 1 , 2 当且仅当g 只，p 2 ，万，b ，- 只 ，这里只是指具有i 个点的路 定理2 2 3 0 ( 【7 l 】) 设g 为n 阶图。则 h ( g ) + ( - ) 一( n + 2 ) + 8 v 画n - + 1 且有无限图族使等号成立 其他参数的关于n o r d h a u s - g a d d u m 型的结果可参阅文献【1 8 ，1 9 ，2 7 ，7 8 ，8 3 ， 8 6 ，8 7 】 2 3 基本拉普拉斯特征根符号和主要结果 设g = ( ke ) 是具有n 个顶点的简单连通图( 不含环和多重边) ，其中v ( a ) = p “忱，) 表示点集合图g 的邻接矩阵定义为个 n , x l l , 矩阵a ( g ) = ( ) ， 其中当点和相邻时a o = 1 ；当和不相邻时啦j = 0 假如g 是个简 单图，则a ( g ) 是个实对称的( 0 ，1 ) 矩阵且它的主对角线上的元素全为零从而 它的实特征根全为实数令d 陬) = 函表示顶点啮的度，图g 的拉普拉斯矩阵 定义为l ( g ) = d ( g ) 一a ( g ) ，其中d = d ( g ) = d i a g ( d ( v 1 ) ，d ( 抛) ，d ( ) ) 是 图g 的度对角矩阵对图g 的每一条边，取其一个端点为始点，另个端点为 终点，这一过程称为给图g 一个定向当图g 取定一个定向时，其定向关联矩 阵定义为q = 口( g ) = ( 哟) ，其中， 则l ( g ) = q ( g ) q ( g ) t ( 其中q ( g ) t 是矩阵q ( g ) 的转置矩阵) 且l ( g ) 与g 的 定向无关( 见【8 】p 1 6 8 ) 容易证明l ( a ) 是一个半正定的，对称的实矩阵且它的 每一行的行和为零，因此，l ( g ) 又是奇异的由g e r g o r i n 8 定理，很容易可以 得知拉普拉斯矩阵l ( g ) 的特征根均为非负实数对一个nxn 维矩阵m 的特征 时时点点始终的的 留勺 边边 是是 耽地岜 当当其 1 l 一 仉 ，_ll-f1i_-_、 1 1 2 0 0 7 年上海大学硕士学位论文 1 4 根，我们一般用符号a l ( m ) ，a 2 ( m ) ，k ( m ) 来表示则对一个图g 来说，我 们用符号九( g ) = 九来表示丸( 五( g ) ) ，l = 1 ，2 ，佗，并且不失一般性，我们假设 a 1 ( g ) a 2 ( g ) k l ( a ) k ( g ) 且称k ( g ) 为图g 的第七大的拉普 拉斯特征值特别地，我们称a 1 ( g ) 为图g 的拉普拉斯谱半径，记为a ( g ) 对 任意图g ，有k ( g ) ；0 ，且特征根为。的重数等于图g 的分支数( 见【7 2 】) 在文 献【5 1 】中，f i e d l e r 证明，图g 是连通的当且仅当图g 的第二个最小的拉普拉斯 特征值k 一1 ( g ) 0 因此，k 一1 ( g ) 被f i e d l e r 称为图g 的代数连通度，记为 o ( g ) 若召是n 阶图g 的补图，令厶和厶分别表示他阶单位阵和元素全为i 的竹阶方阵，则有l ( g ) + l ( 召) = n 厶一厶从而有a ( g ) + o ( 召) = n ，即图的拉普 拉斯谱半径和图的代数连通度是可以互推的从这个意义上来说，图的拉普拉斯 谱半径和代数连通度具有同等的重要性设s 是实数域上的某一区间，用m a ( s ) 表示落在该区间上图g 的拉普拉斯特征值的重数 近年来对拉普拉斯特征根主要集中在研究拉普拉斯谱半径和代数连通度的一 些界以及和图中其他参数的关系方面下面我们给出相关的主要研究结果 关于拉普拉斯谱半径可达上界方面的研究自1 9 8 0 年以来主要有以下结果， 定理2 3 1 ( 【8 4 】) a n d e r s o n 和m o r l e y 的界， a ( g ) m a x d + d j ：e ( g ) ，( 2 3 1 ) 若g 是连通的，则等式成立当且仅当g 是偶正则图或g 是偶准正则图 定理2 3 2 ( 【4 1 】) 李炯生和张晓东的总是比( 2 3 1 ) 好的界- a ( g ) 2 + p 一2 ) ( s 一2 ) ， ( 2 3 2 ) 其中r = m n 茹 吨+ 而：地吻e ( g ) ，8 = m a x d q + 而：q e ( g ) 一 仇) ， 魄e ( g ) ，且以+ 如= r 定理2 3 3 ( 【7 3 】) m e r e s 的界 a ( g ) m n z 也十7 m ：地y ( g ) ) ，( 2 3 3 ) 而 其中砚是指与点钝相邻接的点的度的平均值，即砚= 竺等 2 0 0 7 年上海大学硕士学位论文1 5 定理2 3 4 ( 【4 2 】) 李炯生和张晓东的另一个总是比( 2 3 3 ) 好的界t 水) 坐塑筹掣：玩吩叫g ) ) ( 2 3 4 ) 定理2 3 5 ( 【6 4 】) r o j o 等人的一个总是不超过n 的界， a ( g ) 懈 反+ 由一l 贼n n j i ：纯) ， ( 2 3 5 ) 其中肌= ：q e ( g ) 定理2 3 6 ( f 4 3 】) 李炯生和潘永亮的界 定理2 3 7 ( 3 9 1