（运筹学与控制论专业论文）一般冠图的谱及其相关指数.pdf

摘要 图同谱和同构问题一直是图论研究的重要问题，许多作者对其进行了 广泛的研究并成功地构造出一些同谱图和同构图能量的刻画和计算是 图论中的一个重要的应用。图的w i e n e r 指数和p j r 指数是图论中两个应 用比较广泛的指数本文在前人工作的基础上，对g =u 毗og i 型冠 t = l u i e y ( g o ) 图的邻接谱，l a p l a c i a n 谱以及无符号l a p l a c i a n 谱进行了刻画并构造出无 穷多个同谱但不同构的冠图给出了简单冠图的能量及其能量的界在图 的w i e n e r 指数和p j 指数已有结论的基础上，计算出g =u“；og ；型 i = l v ( a o ) 冠图的w i e n e r 指数以及几类特殊冠图的p ，指数本文将就以下几个方 面进行初步的探讨： ( 1 ) 冠图的邻接谱，l a p l a c i a n 谱和无符号l a p l a c i a n 谱 ( 2 ) 具有( s r ) 性质的二部图的结构特点 ( 3 ) 简单冠图的能量和能量的上、下界 ( 4 ) 冠图g = uu og i 的w i e n e r 指数 t = l 。l e v ( g o ) ( 5 ) 几类特殊冠图的p ，指数 关键词：邻接谱；l a p l a c i a n 谱；无符号l a p l a c i a n 谱；冠图；能量；( s r ) 性质；p i 指数；w i e n e r 指数 a b s t r a c t i ti sa l w a y sa ni m p o r t a n tf i e l do nt h ec o - s p e c t r u ma n di s o m o r p hi nt h et h e - o r yo fg r a p h s m a n yw r i t e r sh a v er e s e a r c h e di t i nag r e a tq u a n t i t ya n dt h e yh a v e s u c c e s s f u l l yc o n s t r u c t e ds o m eg r a p h sr e l a t e dt oc o - s p e c t r u ma n di s o m o r p h a sw e k n o w ，i ti sas i g n i f i c a n ta p p l i c a t i o na b o u tc o m p u t i n gt h ee n e r g yo fg r a p h si nt h e t h e o r yo fg r 印h s b a s e do nt h er e s e a r c h e so ft h ep r e v i o u sw r i t e r s ，t h i sp a p e rh a sd i s - c u s s e dt h ec o m p u t a t i o nf o rt h ea d j a c e n c ys p e c t r u m ，l a p l a c i a ns p e c t r u ma n ds i g n n l e s sl a p l a c i a ns p e c t r u mo ft h ec o r o n ag r a p h si nt h et y p eo fg = u地0g ia n d t = l “i e v ( c o ) c o n s t r u c t e di n f i n i t ec o - s p e c t r u mb u tn o n - i s o m o r p hg r a p h s a l s ot h i sp a p e rc a l c u l a t e s t h ee n e r g ya n dt h eb o u n do fe n e r g yf o rt h es i m p l ec o r o n ag r a p h s o nt h eb a s i so f t h ec o n c l u s i o no ft h ew i e n e ri n d e xa n dp ii n d e x ，t h r o u g hc a l c u l a t i n gw i e n e ri n d e x n t ot h ec o r o n ag r a p h so fg= u u i0g ia n dp ii n d e xo fs o m es p e c i a lc o r o n a ；= 1 u t e v ( g o ) g r a p h s t h i sp a p e rw i l lg i v em yi n i t i a ls t u d ya st ot h ef o l l o w i n ga s p e c t s ( 1 ) t h es p e c t r u mo fa d j a c e n c ym a t r i x ，l a p l a c i a na n ds i g n l e s sl a p l a c i a ni nt h e c o r o n ag r 印h s ( 3 ) t h es t r u c t u r ea n dc h a r a c t e r i s t i co fab i p a r t i t ew i t hp r o p e r t y ( s r ) ( 4 ) t h ee n e r g ya n dt h eb o u n do fe n e r g yf o rt h es i m p l ec o r o n ag r a p h s n ( 5 ) t h ew i e n e ri n d e xo fg =u u i0g t = 1 u i e v ( g o ) ( 6 ) t h ep la n dp li n d e xo fs o m es p e c i a lc o r o n ag r a p h s k e yw o r d s ：a d j a c e n c ys p e c t r u m ；l a p l a c i a ns p e c t r u m ；s i g n l e s sl a p l a c i a n s p e c t r u m ；c o r o n a ；e n e r g y ；p r o p e r t y ( s r ) ；p ii n d e x ；w i e n e ri n d e x i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的研究成果除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明本人完全意识 到本声明的法律后果由本人承担 学位论文作者签名： 导、仁知产年多月确 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，研究 生在校攻读学位期间论文工作的知识产权属湖南师范大学，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅本人授权湖南师范大学可以将学位论文的全部或部分内容编 人有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密彤 ( 请在以上相应方框内打“ ”) 作者签名： 导师签名： 日期斯( 月缅 日期：纠年月日 l 一般冠图的谱及其相关指数 1 绪论 1 1 冠图的谱及其相关指数 图的谱确定问题是图论中的一个重要问题，主要涉及图的邻接谱，图 的l a p l a c i a n 谱以及图的无符号l a p l a c i a n 谱的研究，其研究的主要途径是 通过图的矩阵( 邻接矩阵或l a p l a c i a n 矩阵) 表示，建立图的拓扑结构( 特 别是图的各种不变量) 和图的矩阵表示的置换相似不变量之间的联系，通 过矩阵论，以及组合矩阵论中的经典结论，用于图的拓扑结构的研究 符号图与社会心理学中的社会平衡理论有着紧密的联系符号图最先 由h a r a r y 1 】引入，z a s l a v s k y 将图的拟阵推广到符号图的拟阵 2 1 c h a i k e n 3 与z a s l a v s k y 2 分别得到了符号图的矩阵树定理符号图的最新研究结果 可参看文献【4 1 2 h a r o l dw i e n e r 在1 9 4 7 年用数学语言定义了一个图的w i e n e r 指数 1 1 3 h o s o y a 定义了w i e n e r 多项式，我们习惯上称之为h o s o y a 多项式w i e n e r 指数是计算图中顶点间距离最重要的拓扑指数图的w i e n e r 指数是在化 学中最先使用的拓扑指数，特别在分子化学以及物理化学研究领域起着 重要的作用 1 4 - 1 7 】在化学中w i e n e r 指数等于分子中所有最短的碳碳键 形成的路的总和d o b r y n i n 和其他作者对w i e n e r 指数以及它的应用作了 广泛的研究 1 8 - 1 9 p a d m a k a r i v a n 最先给出p j 指数的定义，p j 指数的数学性质在物理 化学以及纳米结构领域中有着广泛的应用例h y o u s e f i a z a r i ，b m a n o o c h e h r i a n ，a r a s h r a f i 对p ，指数进行了广泛的研究1 2 1 - 2 4 硕士学位论文 1 2 概念与记号 本论文只研究简单无向图和( 无向) 符号简单图f 矧，在下面的论文中 我们将无向符号简单图称为符号简单图设g = ( v ( g ) ，e ( g ) ) 是一个简单 无向图，其点集和边集分别是y ( v ) 和e ( g ) ，令v ( g ) = 【1 ，2 ，礼 图g 的邻接矩阵定义为a ( g ) = ( a i j ) ，这里 f 1 i j 啦户to z 和j 多项式p a ( c ) ( a ) = d e t ( m a ( g ) ) ( 或兄( g ) ( p ) = d e t ( # i l ( g ) ) ，定义为g 的 邻接特征多项式( 或l a p l a c i a n 特征多项式) ，其中，是单位矩阵，图g 的 谱定义为：盯( g ) = ( a z ( g ) ，a 2 ( g ) ，k ( g ) ) ，入- ( g ) x 2 ( 0 ) a 。( g ) ，其 中入。( g ) ，a z ( g ) ，入。( g ) 分别为a ( g ) 的特征值a ( g ) 中最大的特征值称 为g 的谱半径，记作p ( g ) 如果g 是连通的，则a ( g ) 是不可约的，那 么g 的谱半径重数为1 并且由一个正特征向量确定这个正特征向量称 为p e r r 帆向量如果a ( g ) 是奇异的，我们称g 是奇异的矩阵l ( g ) = d ( g ) 一a ( g ) 称为图g 的l a p l a c i a n 矩阵，其中d ( g ) 是n 扎阶的顶点度 对角矩阵g 的l a p l a c i a n 谱我们记作：s ( g ) = ( 9 1 ( g ) ，能( g ) ，( g ) ) ，这里 ，y l ( g ) 7 2 ( g ) ( g ) ，其中1 1 ( g ) ，忱( g ) ，( g ) 为l ( g ) 的特征值 对于任何图g ，7 。( g ) = 0 对应全为1 的特征向量，记作：1 l ( g ) 是半正定 矩阵f i e d l e r 在文献【2 6 】中指出l ( g ) 中第- - i j , 的特征值为0 当且仅当图g 不是连通图l ( g ) 中第二小的特征值称为代数连通度，记作口( g ) q ( g ) 对 应的特征向量称为f i e d l e r 向量矩阵a 的转置记作：，( a d t = a 对于 任意图g ，对应着一个i y ( g ) i i e ( g ) i 的矩阵，称为图g 的关联矩阵设 v 2 ，和e l e 2 ，e m 分别表示图g 的顶点和边，则g 的关联矩阵是 指m ( g ) = 【m 巧】，其中m 西是仇与e j 相关联的次数矩阵q ( g ) = d ( g ) + a ( g ) 称为图g 的无符号l a p l a c i a n 矩阵在本论文中图g 的无符号l a p l a c i a n 矩 阵用q ( g ) 表示q ( g ) = d ( g ) + a ( g ) = u u r 2 7 1 图g 的无符号l a p l a c i a n 谱 2 一般冠图的谱及其相关指数 我们记作：( g ) = ( ，y 1 ( g ) ，7 2 ( g ) ，h ( g ) ) 这里7 1 ( g ) 7 2 ( v ) ( g ) 其中，y 1 ( g ) ，能( g ) ，( g ) 是q ( a ) 的特征值t h o m a sz a s l a v s k y 在文献 【2 5 】中定义了符号简单图，设图g 是一个无向简单图，对图g 中的每条边 进行 + 1 ，一1 ) 标号，这样作成的图我们称为符号简单图，为区别起见，我 们将符号简单图记作如图1 一i ：g 是一个简单图，是一个符号简单 图，= ( g ，盯) ，盯是一个符号函数： 图l 一1 + 甲1 在符号简单图中如果所有的边都被标号为+ 1 ，那么就是一个简单图， 我们称其为符号简单图的底图并记作：l i 符号简单图的邻接矩阵定义 f 1 一加巧= + 1 为a ( e ) = ( n 幻) ，这里锄j = 一1i j ，e 嵇= 一1 【o io oj i i = ( k e ) ，= ( 1 i ，盯) ，这里y 表示i l 的顶点集，e 表示i l 的边集，仃 是一个符号函数，盯：e 一 + 1 ，一1 ) 符号简单图中，对于任意的顶点 口y ( ) ，我们用如( 口) 表示中顶点的度，用+ 表示中所有正边 及其关联顶点所构成的子图，用一表示中所有负边及其关联顶点所 构成的子图，这里的正边是指被标号为+ l 的边，负边是指被标号为一1 的边，用如+ ( 口) 表示+ 中顶点秽的度，如一( 口) 表示一中顶点u 的度，用 d w i ( u ) 表示底图i l 中的顶点u 的度显然d l l ( 口) = d r + ( 秽) + d s 一( 秒) 如果 的所有边都有相同的符号，那么称是齐次的否则称是非齐次的 如果+ ，一都是正则图，那么是正则的陶途径w = e l e 2 e l ，我们 将的符号记作：盯( ) 盯( w ) ：= 口( e 。) 仃( e 。) 盯( e f ) 圈是图中的闭路，长为 n 的圈记作：g ，g = v l v 2 v n l v n v l ，我们将g 的符号记作：口( g ) ，口( g ) ：= 0 ( c 1 , 2 ) 口( e 。，。) o ( e n , 1 ) 如果中每个圈的符号都是+ 1 ，那么称是平衡 3 硕士学位论文 的否则称是不平衡的如果一是平衡的，那么我们称是反平衡的 秒是一个转换函数，口：v _ 十，一) ，的口转换记作：掣，在此我们不妨令 ：= ( i l ，盯) ，8 = ( i i ，0 - 0 ) ，其中( v w ) ：= p ( 口) 盯( e 叫) 护( 伽) 给定任意两个 图g 和日，令v ( g ) = 【l ，2 ，礼 先将日进行n 次复制，然后将第i 个日 中的所有顶点与g 中的第i 个顶点相连接，这样构造的图我们称为g 和 日的冠图，记作go 仃阐如果h = k 。，那么我们称go 虬为简单冠图如 果g oh 是符号简单图，在本论文中我们称g o 日为符号简单冠图如图 1 2 , g = c 3 ，h = k 2 ，冠图go 日，日og 表示如下： 图士一2 对于任意的连通图g 和任意的r 正则图h ，g oh 的谱由g 和日的谱确 定goh 的l a p l a c i a n 谱由g 和日的l a p l a c i a n 谱确定，特别地这里不要 求h 为r 正则图【矧a 是图g 的特征值，如果 也是图g 的特征值，我们 称图g 具有( r ) 性质如果入和- i 有相同的重数，我们称图g 具有( s r ) 性质表示礼个顶点的完全图k ，。表示n 个顶点的星图令r = h 】，s 是一个矩阵ros 表示冗与s 的克罗内克积ros 定义为分块矩阵h 翻 龟= o ，0 ，0 ，1 ( 们，0 ，o 图g 和图日的笛卡尔积记作：g h 并且 v ( gxh ) = v ( v ) y ( 日) 如果a = b 且x y e ( 日) ，或者z = y 且a b e ( g ) ， 男5 么( a ，z ) ( 6 ，y ) e ( g 日) 4 伞 一般冠图的谱及其相关指数 设g 是一个连通的简单无向图，d ( x ，y ) 或d ( x ，可i g ) 表示图g 中顶点z 与y 之间的距离对g 中任意的两个顶点z 和y , d ( x ，y ) 或d ( x ，秒i g ) 定义 为z 和y 之间的最短路径所包含的边数只要g 是连通的，d ( x ，y ) 总是存 在的d ( v ) 或d ( vig ) 表示顶点钉到图g 的距离，并且d ( v ) 满足下列关系 式：d ( 钉) = d ( vlg ) = d ( v ，x l c ) 3 0 ，图的w i e n e r 指数定义为图g 中所 z y ( g ) 有顶点对之间的距离的和图的w i e n e r 指数记作w ( g ) 或w ，w 满足下列 关系式：w = w ( g ) = i 1 d ( v l g ) 令顶点u 和顶点u 在g 中是相邻 t ，y ( g ) 的，e = ( u ，u ) ，e 是连接u 和钞的一条边玩( e ) 是图g 中到顶点扎的距离比 到顶点 的距离小的顶点的集合b y ( e ) 是图g 中到顶点u 的距离比到顶 点u 的距离小的顶点的集合尻( e ) ，鼠( e ) 也可写成集合的形式：玩( e ) = 如i z y ( g ) ，d ( x ，u ) d ( x ，u ) 】，b y ( e ) = zlx y ( g ) ，d ( x ， ) d ( x ，u ) g 是n 个顶点的简单无向连通图，t h o r n 图口是在图g 的第i 个顶点处悬挂只 个孤立点构成的图，其中p i 0 ，i = l ，2 ，n 特别地，若只= r n ，r 为 常数，n 是图g 中第i 个顶点的顶点度若g 是树，那么d ( g ) 与d ( g + ) 之 间满足线性关系：d ( 9 ) = ( r 一1 ) 2 d ( g ) + ( r 一1 ) n + 1 】2 【3 0 】设图g 是一个连 通图，u ，v 是图g 中的顶点，边e = u 秽我们将图g 中到顶点u ，u 距离不相 等的边的总和定义为p 厶指数图g 的p 厶指数记作：p i e ( g ) 我们将图g 中到顶点u 的距离比到顶点口的距离小的边的总数记作t t 。( e l c ) 将图g 中到顶点钞的距离比到顶点u 的距离小的边的总数记作h e y ( e l c ) p i 。( c ) 满足下列等式：p i o ( c ) = 【n e u ( e l y ) + h e y ( e l c ) 1 3 从等式可以看出：图g e e ( g ) 中距离两个顶点相等的边是没有计算在其中的在图g 中e = u v ，我们将 图g 中到顶点让，u 距离相等的边称为e 的平行边g ( e ) 表示图g 中e 的 平行边的总数图g 是一个连通图，u ，口是图g 中的顶点，边e = u u p l 指 数是指图g 中到顶点让，v 距离不相等的顶点的总数n 缸( e l c ) 表示图g 中 到顶点u 的距离比到顶点秒的距离小的顶点的总数n v ( e i c ) 表示图g 中 到顶点v 的距离比到顶点u 的距离小的顶点的总数图g 的p ，点指数 5 硕士学位论文 记作：p 厶( g ) p i ( g ) = 【n u ( e l a ) + ( e i g ) 】帆( e ) = xiz y ( g ) ，d ( x ，u ) e e ( g ) d ( z ，口) ) ，眠( e ) = zz y ( g ) ，d ( x ，u ) d ( x ，u ) 3 2 1 在本论文中将p 厶和p l 指数合称为p ，指数 1 3 冠图的谱、能量及相关指数的研究现状 下面列举出冠图的邻接谱，l a p l a c i a n 谱以及( s r ) 性质的已有结果 1 对于任意图g 1 与r 正则图g 2 ，冠图g = g 。og ：令盯( g 1 ) = ( 肛1 ，p 2 ，p 几) ，a ( a z ) = ( 叩1 ，仇，= r ) 男5 么 郴卜r 1r 2 ：= 1 竽1 i 竿) n 佗工 ， 矩阵中第一行是冠图g oh 的特征值，第二行是特征值对应的重数并且 p ( g ) ：型丝辱围匝 2 9 1 2 g 1 ，g 2 为任意图，g = g 1og 2 令s ( a 1 ) = ( 0 = v 1 ，沈，) ，s ( a 2 ) = ( 0 = j - ，如，如) 那么 s c g ，= ( 如：1 ：如：1 矩阵中第一行是冠图g oh 的l a p l a c i a n 特征值，第二行是特征值对应的 重数同时 ( i ) 1g s ( g ) 当且仅当g 2 是连通图 ( i i ) m + 1 s ( g ) ( i i i ) n ( g ) = 一a ( g 1 ) + r a + l - 4 ( a ( a 21 ) + m + 1 ) 2 - 4 a ( g 1 ) 1 例 3 具有( s r ) 性质的树的结构特点例 4 具有性质( s r ) 的单圈图吼 6 节 一般冠图的谱及其相关指数 5 如果g 为g 的t h o r n 图，p i 0 ，i = 1 ，2 ，佗，那么d ( a ) = d ( a ) + 慨+ 功) d ( u ，吩i g ) + 册) d ( 啦，吻j g ) + ( 鼽) 2 + ( n - 1 ) 鼽i p ：d ( g ) = l i j s n 1 s l 棚5 么) t i - - 一业巡粤堑 地 r 所以p ( g ) ：m a x 盯( g ) ：p ( g o ) + r + v _ r 广- p ( g o ) ) 2 一+ 4 m 口 若g t 均为m 个顶点r 正则图且g 1 = g 2 = = g 住，定理3 1 1 即转 化为文献【2 9 】中的定理1 1 定理3 1 2 对于任意符号简单图o 与m 个顶点的- 正则图i 。i ( z = n 1 ，2 ，礼) ，符号简单冠图=u地o 令a ( ：c o ) = ( p 1 ，p 2 ，卢n ) ，仃( 1 f i ) l = j u y ( e 0 ) 1 4 一般冠图的谱及其相关指数 = ( 叩f ，谚，榭：r ) 又令a i ：型二圭丛竽( i = 1 ，2 ，n ) ( ，) 如果 是平衡的，那么： 盯( ) ：f ，叩i 1 1 7 7 p 覆1 1 杉7 7 三- 叼辨- a - 厶、7 1 11 1 1 11 1 ， ( ，) 如果o 是不平衡的且u o ，( i = 1 ，2 ，n ) 是平衡的，那么： 嘏) ：似，7 ，戎栏t 栏a a n 、7 1 1l 1 1 l1 1 ， 盯( ) 中第一行是符号简单冠图=u啦o t 的特征值，第二行是特 t = 扯t y ( e 0 ) 征值对应的重数并且p ( ) ：丝丛旦 譬坐业塑 证明：由引理2 4 ，2 5 可知如果符号简单冠图是平衡的，那么可 以转换为全为正边的图，即图i i ，并且a ( e ) = a ( i e i ) ，从而和f j 有着 相同的邻接谱由定理3 1 1 可知结论( ，) 成立u o f ，( 待1 ，2 ，礼) 是平 衡的，由引理2 5 可知：o i 可以转换为u toi t i ，( i = 1 ，2 ，他) ，即蛳o i 中不含标号为一1 的边由引理2 5 可知a ( e ；) = a ( i ij ) ，仿照定理3 1 1 中 利用特征向量构造特征值的方法可得出结论( ，) 成立口 为了更好地说明定理3 1 2 ，如图3 3 ：o = ( 岛，6 r 1 ) ，1 = ( k 2 ，叻) 饥，o 2 均为符号函数 一1 。_ _ - - - - _ _ _ _ - - _ 。_ l 图3 3 在上图中o 是不平衡的符号简单图，令y ( o ) = ( u - ，u z ，u 3 ) ，u to z 是平衡 1 5 硕士学位论文 的o 的邻接特征值为：一2 ，1 ，1 ，i ti 的邻接特征值为：一1 ，i , e oo 。的邻接特 征值为：一z 雩越，一1 ，一1 ，一1 ，1 一以，1 一以，雩玉，i + 以，l + 以 推论3 1 3 对于任意图g o 与m 个顶点的r 正则图g ( i = 1 ，2 ，n ) ， v ( a 。) ： u 。，仳2 ，u n ) ，v ( a ；) ： 口珐谚，铡 冠图g ：l = j t i 。 u i e v ( g o ) g 我们按如下方法构造符号简单冠图：对图g 0 进行任意的( + 1 ，一1 ， 标号标号后的g o 记作；( g o ，e ) ，其中e 为符号函数对于任意的u ； v ( g o ) ，t y ( g ) ，我们将e 以及g i 中的每条边都标号为+ 1 ，0 = 1 ，2 ，n ) ，0 = 1 ，2 ，m ) ，这样标号后的g ，g o ，g i 分另, 1 i 5 作：，o ，t 并且 = o t 正io i 令盯( o ) = ( 口l ，q 2 ，a n ) ，盯( i 。i ) = ( ，7 i n ，孝，? 7 船= r ) 1 = l 吣e y ( e o ) 又令a = a i + r + ( 下r - 一a i ) 2 + 4 m l 1 z = l ，2 ，n ) ，那么： 盯( ) ：一刀p 瑾栏栏ta a 、7 1 11 l l 11 1 ， 伊( ) 中第一行是符号简单冠图=u u io t 的特征值，第二行是特 = 1 u t y ( e o ) 征值对应的重数并且p ( ) ：坐丛旦 譬丝坚 证明：由定理3 1 2 可直接得出结论口 推论3 1 4 对于任意图g o 与m 个顶点的r9 - 9 1 j 图g i 0 = 1 ，2 ，礼) ， v ( g o ) = u 1 ，札2 ，乱。) ，v ( g ) = 口，谚) ，u 辖 冠图g = i ：i 乱i og i 1 = j u t y ( g o ) 我们按如下方法构造符号简单冠图；对图g o 进行任意的 + 1 ，一1 标号 标号后的g o 记作：( g o ，e ) ，其中e 为符号函数，这里( g o ，e ) 可以是平衡 的，反平衡的或者是不平衡的对于任意的讹v ( a o ) ，口：v ( g i ) ，我们 将e 。o t ) 标号为+ 1 ，g 中的每条边都标号为一1 ，即g 为反平衡的“= 1 ，2 ，n ) ，0 = 1 ，2 ，m ) ，这样标号后的g ，g o ，g 分别记作：，o ，i 并且 = 0讹o i 令盯( o ) = ( 卢。，仍，风) ，o - ( 1 t 1 ) = ( 叩f ) ，槿，槲= ，) t = j 缸e v ( z o ) 1 6 一般冠图的谱及其相关指数 又令a ：丝兰堑霉g ：l ，2 ，佗) ，那么： 哂，= ：- o 三1 - 譬1 譬) 盯( ) 中第一行是符号简单冠图：l 二f讹。的特征值，第二行是特 t = 1 q y ( o ) 征值对应的重数 证明：仿照定理3 1 1 的中利用构造特征向量求特征值的证明方法： 已知夙，仍，风是a ( e o ) 的特征值，令x 。，恐，k 分别是这些特 征值对应的正交特征向量墨姊表示向量五的第k 个分量，( 洁1 ，2 ，佗k ： 1 ，2 ，n ) 设扎0 = 1 ，2 ，扎) 为冠图g 的n 个邻接特征值设可譬为所 对应特征向量的第n + ( 七一1 ) m + t 个分量，( k = 1 ，2 ，n 亡= 1 ，2 ，m ) 由 冠图的构造特点以及g 是m 个顶点的r 正则图可知：堙= 纡= = 不妨令娠c t ) = y k ，( k = 1 ，2 ，n 江1 ，2 ，m ) 由引理2 1 可知： 兰二群铲 由上面的式子，我们可以得到：挑= 筹以及九：坠竺丛乒堂堂，元： 坠= 丛生2 她( i ：l ，2 ，n ) ，a i , 元的特征向量分别为： ( 五，南五，南咒) ，( 五，赤x ，蒋1x ) 1 谚订为a ( i t i ) 的 邻接特征值，o = 1 ，2 ，m 一1 i = 1 ，2 ，n ) 因为i ；i 是m 个顶点的r 正则图且是反平衡的，可以得出一，7 ，为a ( e ；) 的邻接特征值设硝是 一叩5 所对应的特征向量因为： a c ，( 刁；，乙岛) = 一孝( 零，乙e 。) 所以一嘭也是a ( ) 的特征值o = 1 ，2 ，m 一1 i = 1 ，2 ，他) 令 1 7 硕士学位论文 a ：坚唑霉( i _ 1 2 ，2 ，佗) ，那么： 啦，= - 三1 _ 呼1 口 推论3 1 5 对于任意图g o 与m 个顶点的r 正则图g i ( i = 1 ，2 ，n ) ， v ( c o ) = 让。，缸2 ，) ，y ( g ) = i 订，u ，嘏) 冠图g = ( ：j 讹o l = 1 “t e v ( o o ) g ；我们按如下方法构造符号简单冠图j 对图g 0 进行任意的 + 1 ，一1 ) 标 号标号后的g o 记作- ( c o ，e ) ，其中e 为符号函数，这里( g o ，e ) 可以是平衡 的，反平衡的或者是不平衡的对于任意的乱；v ( c o ) ，u v ( c i ) ，我们 将e ，( ) 标号为一1 ，g 中的每条边都标号为一1 ，即g 为反平衡的( z = 1 ，2 ，n ) ，o = 1 ，2 ，m ) ，这样标号后的g ，g o ，g 分别记作? ，o ，i 并且 ： l ：i让t 。i 令仃( o ) = ( p 1 ，尾，风) ，叮( i i i ) = ( ，7 ，? 7 ，刀黝= r ) i = 1 u i e v ( z ：o ) 又令a i ：生兰丛坐塑( i ：1 ，2 ，礼) ，那么： 睢，= - ， 一，摄三。一蠢2 。a 。 11l ) 盯( ) 中第一行是符号简单冠图：o让。；的特征值，第二行是特 i = l q y ( e 0 ) 征值对应的重数 证明：仿照定理3 1 1 的中利用构造特征向量求特征值的证明方法： 已知历，岛，风是a ( o ) 的特征值，令墨，咒，分别是这些特 征值对应的正交特征向量曩表示向量五的第k 个分量，( i = 1 ，2 ，n k = 1 ，2 ，n ) 设九( 江1 ，2 ，n ) 为冠图g 的扎个邻接特征值设为九所 对应特征向量的第佗+ ( 七一1 ) m 4 - 个分量，( 七= 1 ，2 ，礼t = 1 ，2 ，m ) 由 冠图的构造特点以及g ；是m 个顶点的r 正则图可知：毋= 可：2 ) = = ! ， 1 8 一般冠图的谱及其相关指数 不妨令簇= y k ，( k = 1 ，2 ，n t = 1 ，2 ，m ) 由引理2 1 可知： f 九耐奄) = 讹砖一m y 知 l 九弧= 一7 - 鲰一砖砷 由上面的式子，我们可以得到：纨= 一筹以及九= 坠兰近型2 坚，元= 生三丛竺竺( t = 1 ，2 ，礼) ，九，元的特征向量分别为： ( x ，一赤五，一寿五) 2 ，( 五，一南k ，一六五) 2 矽为a ( i t 1 ) 的邻接特征值，0 = 1 ，2 ，m 一1 i = 1 ，2 ，n ) 因为i 一是m 个顶点的r 正则图且是反平衡的，可以得出一叩5 为a ( e ；) 的邻接特征值设硝是 一嘭所对应的特征向量因为： a c ，( 刁；，：e ；) = 一叩j 。( 刁。：岛) 所以一叼j 也是a ( ) 的特征值o = 1 ，2 ，m 一1 i = 1 ，2 ，n ) 令 a ：丝簟霉( 江1 ，2 ，2 ，n ) ，那么： 睢，= ：- 弘三1 ：曙1 h 口 设t 是树图，简单冠图to 致仍然是树图因为任何符号简单树图均 是平衡的，所以a ( t ok 。，盯) = a ( i t 。g l l ，盯) ，其中口为任意符号函数在简 单冠图t o 硷中，我们可以对边进行任意的 + 1 ，一1 ) 标号，t ok - 的邻接特 征值不会改变至此我们解决了一般冠图和符号简单冠图的邻接谱问题 3 2 一般冠图和符号简单冠图的l a p l a c i a n 谱 令g o ，g ( = 1 ，2 ，n ) 为任意简单图v ( g o ) = 缸1 ，? 2 2 ，) ，y ( g t ) = 硝们，谬，溯) ( z ：1 ，2 ，n ) 如上节的定义：g ：i 二| u i 。g ；这里 i = j u i y ( g o ) i v ( v t ) i = m g 。，g ：，g 。是具有相同顶点数和顶点度序列的图 1 9 硕士学位论文 定理3 2 1g o ，g i ( i = 1 ，2 ，n ) 为任意图，g =uog i 令 t = j u t v ( o o ) s ( g 。) = ( o = v 1 屹，) ，s ( g i ) = ( o = 6 ，6 ，栅) ，丝二型兰奎厶鲁! 坐 = c i ( i = 1 ，2 ，n ) ，那么 s c g ，= ( 毋1 _ 1 ：毋) 1 + l ：鹋1 - 1 ：衍l + 1 i ) 矩阵中第一行是冠图g =u让tog i 的l a p l a c i a n 特征值，第二行是特 = j q y ( g o ) 征值对应的重数同时 ( i ) 1 乒s ( g ) 当且仅当g 是连通图( i = 1 ，2 ，n ) ( i i ) m + 1 s ( g ) ( 捌) n ( g ) ：，a ( g o ) + m + l - 萼( a ( g o ) + m + 砸1 ) 2 - 4 a ( g o ) 1 证明：设0 = i l l ，v 2 ，是l ( g 1 ) 的特征值，l = m ，蚝，碥是这些 特征值分别对应的特征向量设m ，讯( z = 1 ，2 ，扎) 均为l ( g ) 的特征值 令v ( g ；) = k ， = 1 ，2 ，n ) 设z 夕是特征值m 所对应的特征向量的第 竹+ ( i 一1 ) m + j 个分量，( i = 1 ，2 ，n j = 1 ，2 ，m ) 盔为图g 0 中顶点i 的 度，为g ；中顶点歹u = l ，2 ，m ) 的度 一个分量均为南k ( 1 ) 一个分量均为击m ( 2 ) 一个分量均为击m ( n ) 图3 4 0 我们利用构造特征向量的方法来求特征值首先考虑u 。og 。中的顶点，由 一般冠图的谱及其相关指数 引理2 2 可知： ( d ? + 1 ) x 1 c ) 一z 1 ) 一( 1 ) = h x l 0 ) ，o = 1 ，2 ，m ) ( 3 4 ) t j t k 由( 3 - 4 ) 化简得到 z ( j ) 2 去k ( 1 ) ，o = 1 ，2 ，m ) ( 3 - 5 ) 同理可得：z ：o ) = 去m ( 2 ) ，z 。0 ) = 南m ( 礼)