（应用数学专业论文）图的谱确定问题研究的若干结果.pdf

硕卜学位论文 摘要 “哪些图由它们的谱确定? 的问题于半个世纪前起源于化学1 9 5 6 年，g 讧n t h a r d 和p r i m a s 在篇把图谱理论与化学中h n c k e l s 理论相联系的论文中提出了这个问 题那时，人们认为所有的图都能由它的谱确定但是，一年以后，c o l l a t z 和s i n 伊 g o w i t z 找到了一对同谱图1 9 6 6 年，f i 8 h e r 在考虑k a u c 提出的问题：“一个人能否 听到鼓声的形状 时，用一个图模拟了鼓声的形状，这样，鼓声就可以用图的特征 值刻画实际上，他的问题也是我们研究的问题一个图是谱确定的，简单地说是 指，没有别的不同构的图形具有相同的谱如果存在两个或者更多的图形具有一样 的谱，那么这些图形便是同谱图形所以说，寻找同谱图也是谱确定问题的范畴自 c 0 1 l a t z 和s i n o g o w i t z 找到了一对同谱图后，许多的同谱图已经找到但是，目前对 这个问题的研究成果并不是很多 本文主要研究了一些特殊结构的图形的谱确定问题一一l o l l i p o p 图、多扇图、 多轮图和一类似双星树所谓的l o l l i p o p 图，是在圈图g 上任意一点与路图r p 的一个悬挂点之间添加一条边所得到的图所谓的多扇图，实际上是一种组合图， 记为( r ，+ r 。+ + r 。) 6 ，其中6 是一个泛点，r ，+ r 。+ + r 。是 路图r ；( m 1 ) 的不相交的并( 主= 1 ，2 ，七) 特别地，当七= 1 时，定 义即为经典的单扇图r 1 + 1 与多扇图类似，所谓的多轮图也是一种组合图，记为 ( g 。+ g 。+ + g 。) 6 ，其中6 是一个泛点，g ，+ g ：+ + g 。是圈图 g 。( 七l 且m 芝3 ) 的不相交的并( i = l ，2 ，七) 特别地，当七= l 时， 定义即为经典的单轮图帆1 + 1 如果一棵树有且只有两个顶点度大于2 ，那么这 棵树称为似双星树定义巩( p ，p ) ( 礼2 ，p 1 ) 是一类特殊的似双星树本文 主要研究了l o l l i p o p 图玩，p 的邻接谱确定问题、l a p l a c i a n 谱确定问题和q 一谱 确定问题；多扇图( r ，+ r ：+ + r 。) 6 的l a p l a u c i a n 谱确定问题；多轮图 ( g 。+ g ：+ + g 。) 6 的l a p l a c i a n 谱确定u j 题和似双星树玩( p ，p ) 的l a p l a u c i a n 谱确定问题，主要得到了如下的结果： ( 1 ) 1 0 1 l i p o p 图巩，p 为正奇数) 由它的邻接谱确定 ( 2 ) 图以，p ( p 为正奇数) 由它的邻接谱确定 ( 3 ) l o l l i p o p 图乒k ，p 由它的l a p l a u c i a n 谱确定 ( 4 ) l o l l i p o p 图巩，p 由它的q 谱确定 ( 5 ) 多扇图由它的l a p l a u c i a n 谱确定 ( 6 ) 奇单轮图由它的l a p l a c i a n 谱确定 ( 7 ) 奇多轮图由它的l a p l a c i a n 谱确定 图的谱确定问题研究的若十结果 ( 8 ) 似双星树巩( p ，p ) 由它的l a p l a c i a n 谱确定 关键词：邻接矩阵；l a p l a c i a j l 矩阵；q 一矩阵：邻接谱；l a p l a c i a n 谱；q 一谱；同谱 图；1 0 l l i p o p 图；多扇图；多轮图；似双星树 i i 硕卜学位论文 a b s tr a c t t h eq u e s t i o n “w h i c hg r a p h sa r ed e t e r m i n e db yt h e i r8 p e c t r a ? ”g o e sb a c kf o r h a l fac e n t u r y ，a n do r i g i n a t e 8f 】m mc h e m i s t r y i n1 9 5 6 ，g 讧n t h a r da n dp r i m a sr a i s e d t h eq u e s t i o ni nap a p e rt h a tr e l a t e st h et h e o 巧o fg r a p hs p e c t r at oh 讧c k e l st h e o 盯 行o mc h e m i s t r y a tt h a tt i m e ，a l lg r a p l l sw e r ec o n s i d e r e dt ob ed e t e r m i n e db yt h e i r s p e c t r a b u t ，ap a i ro fe 0 8 p e c t r a lg r 印l l sw e r ef o u n do u tb yc o l l a t za n ds i n o g o w i t z ay e a r1 a t e r i n1 9 6 6 ，f i s h e rw h oc o i l s i d e r e daq u e s t i o no fk a c ：“c a no n eh e a rt h e s h 印eo fad r u m ? ”m o d e l l e dt h es h a p eo ft h ed r u mb yag r a p h t h e n ，t h es o u n d o ft h a td r u mi sc h a r a c t e r i z e db yt h ee i g e l l v a l u e so ft h eg r a p h t h u s ，k a c sq u e s t i o n 远e s 为e n t i a l l yo t l r s a 口a p hi ss a i dt 0b ed e t e r m i n e db yi t ss p e c t r u mi ft h e r ei sn o o t h e rn o n _ i s o m o r p h i cg r a p hw i t ht h es a m es p e c t r u m i ft w oo rm o r eg r a p h sh a v et h e s a n 岭s p e c t r u m ，t h e nt h e s eg r a p l l s 骶。0 s p e c t r a lg r a p l l s t h u s ，6 n d i n gc o s p e c t r a l g r a p l l sb e l o n 伊t ot h eq u e s t i o n “w h i c hg r a p l l sa r ed e t e r m i i 埘b yt h e i rs p e c t r a ? ” m a l l yc o s p e c t r a lg r a p h sw e r ef o u n do u ta f t e rc o l l a t za n ds i n o g o w i t zf o u i l do u tt l l e p a i ro fc o s p e c t r a lg r 印l l s b u t ，a 璐w e r i n gt h i sp r o b l e ms e e m so u to fr e s e a r c h ，n o w i nt l l i st h e s i s ，s o m eg r a p h sw i t hs p e c i a ls t r u c t u r ea r ec o i l s i d e r e d t h el o l l i p o p g r a p h ，d e n o t e db y 风，p ，i so b t a i n e db ya p p e n d i n gac y c l eq t oa p e n d a n tv e r 溆o f ap a t hr p an m l t i f a ng r 印hi sa 铲a p ho ft h ef o r m ( r 1 + r 2 + + r k ) 6 ， w h e r e6i sau n i v e r s a dv e r t e x ，a n dr 1 + r 2 + + r 知i st h ed 两o i n tu n i o no f p a t l l sr ( 他1 ) f o rt = 1 ，2 ，七n o t et h a tt h ep a r t i c u l 盯c a s eo f 尼= 1i nt h e d e f i n i t i o ni sj u s tt h ec l a s s i c a lf a i l 伊a p hr l + 1 s i m i l a rt ot h ei i m l t i - f 如g r a p h ，t h e m u l t i w h e e lg r 印hi st h eg r a p h ( g l + g 2 + + g k ) 6 ，w h e r eg l + g 2 + + g - i st h ed i s j o i n tu i l i o no fc i r c u i t sg t ，a i l d 七l 觚( 1 仇3f o r 待1 ，2 ，七n o t e t h a tt h ep a r t i c u l a rc a s eo f 七= 1i nt l l ed e f i n i t i o l li sj1 1 s tt h ec l a s s i c a ls i n g l ew h e e l g r 印hw k l + 1 at r e ei sc a l l e dd o u b l es t a r l i k ei fi 毒h a u se x a c t l yt w ov e r t i c e so fd e g r e e g r e a 七e rt h a nt w o w bd e n o t eb y 巩( p ，p ) ( n 2 ，p 1 ) o n es p e c i a ld o u b l es t a r l i l ( e g r a p h i nt h i st h e s i s ，w ep r c i v et h a 屯 ( 1 ) 1 0 l l i p o pg r a p h 玩，pw i t hpo d d i sd e t e 咖i n e db y 池a d j a c e n c ys p e c t r u m ( 2 ) g r a p h 以，pw i t hpo d di sd e t e r m i n e db y i t sa d ja c e n c ys p & t r u m ( 3 ) l o l l i p o pg r a p h 风，pi 8d e t e r m i n e db yi t sl 印l a c i a ns p e c t r 啪 ( 4 ) 1 0 1 l i p o pg r a p h 巩pi sd e t e r m i n e db yi t s9 s p e c t r u m ( 5 ) m u t i f a ng r a p hi sd e t e r m i n e db yi t sl a p l a c i a ns p e c t r u m ( 6 ) o d ds i n g l ew h e e lg r a p hi sd e t e r m i n e db yi t sl a p l a c i a ns p e c t r u m 1 1 4 5 i 的谱确定问题研究的若十结果 ( 7 ) o d d m l t i w h e e lg r a p hi sd e 七e r m i n e db yi t sl a p l a c i a ns p e c t m m ( 8 ) g r a p h 风( p ，p ) i sd e t e r m i n e db yi t sl a p l a c i a ns p e c t r u m k e yw o r d s ：a d j a c e n c ym a t r 议；l a p l a u c i a nm a t r i ) 【；q m a t r i ) 【：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 ；q s p e c t r u m ；c o s p e c t r a lg r a p h ；1 0 l l i p o pg r a p h ；m u t i f a n g r 印h ；n m t i - w h e e lg r a p h ；d o u b l es t a r l i k et r e e 硕十学位论史 常用符号 i 符号说明 i g = g ( ke )顶点集合和边集合分别为y ，e 的图g l y ( g )图g 的顶点集 l 刁图g 的补图 l a ( g )图g 的邻接矩阵 i l ( g )图g 的l a p l a c i a n 矩阵 1q ( g )图g 的q 矩阵 ir ( g ) ( a ) = d e t ( 入，一a ( g ) ) 图g 的邻接特征多项式 i 吃( g ) ( p ) = d e t ( 肛，一l ( g ) )图g 的l a p l a c i a n 特征多项式 i ，乙( g ) ( ) = d e t ( ，一q ( g ) )图g 的q 一特征多项式 p 1 p 2 p 。( = o )图g 的l a p l a c i a n 谱 魄屹图g 的q 一谱 a m a x = a 1图g 的邻接谱半径 p m a x2 弘1图g 的l a p l a c i a n 谱半径 a x2 1图g 的q 一谱半径 d 1 如d n图g 的不增度序列 = d 1图g 的最大度 6 = d n图g 的最小度 h+g图g 和不相交的并 日g图g 和日的积 v 蚓的谱确定i u j 题研究的若十结果 插图目录 图1 1 邻接同谱对 3 图1 2 l a p l a u c i a n 同谱对 3 图1 3 最小的q 同谱对3 图2 1 似双星图风( p ，口) 如q 1 ) 1 0 图3 1 l o l l i p o p 图1 1 图3 2同谱图编6 和g 1 6 图3 3 关于邻接矩阵同谱的图c ( 风，6 ) 和g ，：2 1 图4 1 多扇图( r + r t + l + r t + 2 + + r 。) 6 2 4 图4 2 度序列为4 ，4 ，4 ，2 ，2 ，2 的图2 5 图4 3 度序列为4 ，4 ，4 ，3 ，3 ，2 的图2 8 图4 4 度序列为6 ，4 ，4 ，4 ，4 ，2 ，2 ，2 的图2 8 图4 5 度序列为5 ，4 ，4 ，4 ，3 ，2 ，2 的图。3 1 图5 1 似双星树玩( p ，p ) 3 3 图5 2 邻接同涪对吼( 3 ，3 ) 和g ，3 3 v i 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：。湖蚴、1 日期：- r 年彳月i 刀日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同 时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据 库，并通过网络向社会公众提供信息服务。 作者签名：孓1 哆阂t 1 作者签名：跏1 哆阂t1 副i i 签名：带参耳 ，”r 1 日期：o 阵 日期：咯年 石月id 日 6 月fo 日 硕十学位论文 第1 章绪论 1 1 谱确定问题的研究背景 图的谱理论是代数图论中的一个重要课题，主要涉及图的邻接谱与图的l a p l 舻 c i a n 谱的研究其研究的主要途径是通过图的矩阵( 邻接矩阵或l a p l a c i a n 矩阵) 表 示，建立图的拓扑结构( 特别是图的各种不变量) 和图的矩阵表示的置换相似不变 量之间的联系，通过矩阵论，特别是非负矩阵理论和对称矩阵理论，以及组合矩阵 论中的经典结论，用于图的拓扑结构的研究另外，图谱理论也可用于非负矩阵理 论、组合矩阵论和组合数学的研究( 见f 1 1 ，第七章) 图的邻接谱最早起源于量子化学的研究( 见【1 1 ，第八章) h 讧c h e l ( 1 9 3 1 年) 在 对非饱和碳氢化合物的研究中，引进了一种近似处理的方法，产生了对应分子的图 论模型其中图的特征值被用来表示特定电子的能量级自此以后，图的邻接谱引 起了众多的数学家与化学家的广泛研究和利用 1 9 5 6 年，g t i n t h a r d 和p r i m a s 在一篇把图谱理论与化学中h 讧c k e l s 理论相联 系的论文( 见【1 】，第六章) 中提出了“哪些图由它们的谱确定? 这一问题那时， 人们认为所有的图都能由它的谱确定但是，一年以后，c o l l a t z 和s i n o g o w i t z 找到 了一对同谱图 1 9 6 6 年，f i s h e rp 在考虑k a u c 闸提出的问题：“一个人能否昕到鼓声的形状” 时，用一个图模拟了鼓声的形状，这样，鼓声就可以用图的特征值刻画实际上，他 的问题也是我们研究的问题 。 所谓的“谱确定问题”，简单地说是指，根据已有的特征值是否可以确定出唯一 的图形如果存在两个或者更多的图形具有一样的谱，那么这些图形便是同谱图形 所以说，寻找同谱图也是谱确定问题的范畴自c o l l a t z 和s i n o g o w i t z 找到了一对 同谱图后，许多的同谱图已经找到但是，谱确定的图形却知之甚少 1 9 7 3 年，s c h 髓n kh 声明：几乎所有的树都不能由它们的邻接谱确定后 来，c d g o d s i l 和b d m c l 哪证明了几乎所有树的补图都不能由它们的邻接谱确 定州b d m c i 呵还证明了几乎所有的树都不能由它们的l a p l a c i a n 谱确定嘲这 也是最早研究谱确定问题的文章在这些结论后，关于一般的图是否谱确定的问题 就没有统一的结论由于证明谱确定问题的工具的限制，人们只能把目光放在某些 特殊结构的图上，如正则图等直到近十几年，人们才把注意力放到更一般、更复 杂的图形上但是，这些图形仍然受到结构上的限制 几乎所有的图都由它的谱确定? 还是几乎所有的图都不能由它的谱确定? 或者 两者都不是? 迄今为止，n 个顶点的已知的非谱确定图的比例远远大于已知的谱确 定图的比例但当n _ o o 时，这两个比例都趋于零 图的谱确定问题研究的若干结果 目前，问题“那些图由它的邻接矩阵或l a p l a c i a i l 矩阵的特征值确定? ”的研究 结果并不多由于计算机的广泛使用，人们试图通过计算机列举来解决谱确定问题 计算机的计算结果表明大部分1 1 个顶点( 或更少的顶点) 的图是谱确定图但是， 当n 逐渐变大时，计算机很难运算出结果这也是研究谱确定问题的一个重要动机 一一降低计算复杂度 谱确定问题在其它方面也有广泛应用，如：数据挖掘、超大规模集成电路等领 域总之，研究谱确定问题是很有意义的 1 2 概念与记号 在这里，只研究简单无向图设g = ( y ( g ) ，e ( g ) ) 是一个简单无向图，其点集 和边集分别是y ( g ) 和e ( g ) 图g 的补图用虿来表示对任意的秒y ，点u 的 度表示为也图g 的顶点度序列记为d l 如d ，l ，记最大度为= d 1 ，最 小度为6 = 厶 图g 的邻接矩阵定义为a ( g ) = ( n i ，f ) ，这里 二喜篙； 矩阵l ( g ) = d ( g ) 一a ( g ) ( 或q ( g ) = d ( g ) + a ( g ) ) 称为图g 的印j o c t 口佗矩 阵( 或s 细n f e s sl 口p 缸c i o 礼矩阵) ，其中d ( g ) 是n n 的顶点度对角矩阵多项 式j 气( g ) ( 入) = d e t ( a ，一a ( g ) ) ( 或吃( g ) ( p ) = d e t ( p ，一l ( g ) ) ；尸i q ( g ) ( ) = d e t ( j q ( g ) ) ) ，定义为图g 的邻接特征多项式( 或l 印如c i o n 特征多项式；s 匆n f e s s 鲫f n - c i 8 n 特征多项式) ，其中，是单位矩阵设a 1 a 2 k 、m p 2 ( = 0 ) 和岣忱分别是图g 的邻接特征值、二印f n c i 口扎特征值和 s 匆佗f e 船三叩纪c i n 礼特征值图g 的邻接谱( 或却f n c i n n 谱；s 匆扎? e s s 三印地c i n 礼谱) 分别由图g 的邻接特征值( 或l a p l a c i a i l 特征值；s i g n k s sl a p l a c i a n 特征值) 组成 下面，s i g n l e s sl a p l a c i a n 矩阵、s i g n l e s sl a p l a c i a n 特征多项式、s i g n l e s sl 印l a c i a n 特征值和s i g n l e s sl a p l a c i a n 谱简写为q 一矩阵，q 一多项式，q 一特征值和q 一谱 具有相同的邻接谱( 或l 印l a c i a n 谱；q 一谱) 的图形称为邻接同谱图( 或l 印玩 c i o n 同谱图；q 一同谱图) 若图h 和g 具有相同的邻接谱( 或l a p l a c i a n 谱；q 一 谱) ，并且日和g 不同构，则图日称为图形g 的邻接同谱对( 或l 印地c i 口礼同谱 对；q 同谱对) 图1 1 和图1 2 分别给出了一对邻接同谱图p 1 和一对l a p l a c i a n 同谱图。丌文章【7 ，8 】给出了最小的9 同谱对：1 ，3 和恐u 虬，如图1 3 所示 如果两个图形的线图h 关于邻接矩阵同谱，那么这两个图形称为c j 同谱 给定两个图g 1 和g 2 ，图g 称为g l 和g 2 的不相交的并( 或和) ，记为 g = g 1 + g 2 ：若y ( g ) = y ( g 1 ) uy ( g 2 ) 和e ( g ) = e ( g 1 ) ue ( g 2 ) 相似地，g 1 2 硕卜学位论文 和g 2 的积，记为g 1 g 2 是由g 1 + g 2 通过连接g 1 中的每一个点到g 2 中的每 一个点而得到的尤其地，如果g 2 只有一个点6 ，那么g 1 + g 2 和g 1 g 2 缩写 为g 1 + 6 和g 1 6 此时，6 分别称为孤立点和泛点 本文用到的所有概念与符号均可参考专著f 1 ，旷1 2 】 口 au 施硒4 图1 1 邻接同谱对 图1 2l a p l a c i a n 同谱对 凰u 甄k l 。3 图1 3 最小的q 一同谱对 1 3谱确定问题的研究现状 下面，将列举关于谱确定问题的已有成果 1 3 1 邻接谱确定的图形 1 七个不相交的阶为z 的完全图的并尼硒，线图l ( ) ( 仡8 ) 和线图l ( ，m ) ( m 4 ) 及它们的补图，阶为( 3 ，6 ) 的广义四边形的点图等由它们的邻接潜确定刀 2 正则图中，个完全相同的强正则谱确定图的不相交的并及其补图、g 以及 其补图、，g ( 仇，m 一1 ：m 一2 ) 五及其补图由它们的邻接谱确定 3 ：七个不相交的完全图的并。+ 。+ + 。能由它的邻接谱确定，其中 讥1 ，n 2 ，佗七为正整数吲 3 图的谱确定问题研究的若干结果 4 七个不相交的路图的并r 。+ r 。+ + r 。能由它的邻接谱确定，其中佗l ，佗2 ，n 知 至少为2m 5 七个不相交的圈的并g 。+ g ：+ + g 。能由它的邻接谱确定，其中n 1 ，他2 ，佻 至少为3 饥 6 若二部图g 有三个不同的特征值a 1 ，a 2 ，入3 ，重数分别是m 1 ，m 2 ，m 3 ，则入3 ： 一a 1 ，a 2 = o ，m 3 = m 1 且g 是m 1 个完全二部图所汹的直和和仇2 一吕( n + 磁一2 ) 个孤立点，这里n s = a ，i = l ，2 ，m 1 进一步，若图g 是上述图 且增= p ，p 是素整数，则g 由它的邻接谱确定1 捌 7 具有三个邻接特征值且最小特征值为一2 的非正则图中，有5 个能由邻接谱确 定1 引 8 正则完全多部图由它的邻接谱确定 9 路的补图由它的邻接谱确定n q 1 0 图磊能由它的邻接谱确定；图磊的七个不相交的并。+ 。+ + z 由它的邻接谱确定，其中m l ，m 2 ，m 后是至少为2 的整数m 1 1 t 形树t ( z l ，z 2 ，f 3 ) 能由它的邻接谱确定，其中( z l ，z 2 ，2 3 ) ( z ，z ，2 z 一2 ) 且z 2 为整数 1 2 所有最大特征值不大于 i f 万的连通图由它们的邻接谱确定 1 3 i v a n o v - i v a n o v _ 跏a d j e v 图由它的邻接谱确定例 1 4 设g = 乃。+ 乙：+ 十乙。+ z l 正+ 2 死+ t 3 的邻接谱半径入1 2 ，那么 g 由它的邻接谱确定当且仅当g 中不含这样的部分：它们的不相交的并的谱 等于反( i = 1 ，4 ) 阻1 1 5 h 锄m i n g 图日( 3 ，g ) ( g 3 6 ) 由它的邻接谱确定 1 3 2 l a p l a c i a n 谱确定的图形 1 度为o ，1 ，2 ，n 一3 ，佗一2 ，n 一1 的n 阶正则图由它的l a p l a c i a d l 谱确定f 1 】 2 正则图中，个完全相同的强正则谱确定图的不相交的并、，g ( m ，m 一1 ，m ， 2 ) 也、q 以由它们的l a p l a c i a n 谱确定m 4 硕 ? 学位论文 3 后个不相交的阶为f 的完全图的并七硒，线图l ( ) ( 礼8 ) 和线图l ( ，m ) ( 仇4 ) 及它们的补图，阶为( 3 ，6 ) 的广义四边形的点图等由它们的l a p l a c i a n 谱确定忉 4 七个不相交的路图的并r 。+ r ：+ + r 。由它的l a p l a c i a n 谱确定，其中 佗1 ，砌，扎七为正整数m 5 七个不相交的圈的并g ，+ g ：+ + g 。由它的l a p l a c i a n 谱确定，其中 亿1 ，n 2 ，仃七至少为3 吲 6 图帆，死，七磊由它们的l a p l a c i a n 谱确定。1 7 1 7 设g = 乙，+ + + 乙。的邻接谱半径a 1 1 个顶点，等号成立当且仅当( g ) = 仃一1 ，其中( g ) 是g 中的 最大顶点度，p m 戤( g ) 是g 的最大l a p l a c i a n 特征值 引理2 o 1 2 例设g 有哆个顶点，d = ( d l ，d 2 ，如) 是它的不增度系列，其 最大q 一特征值为觚，那么 2m i n d 1 ，c f 2 ，厶) 献2m a x d l ，d 2 ，厶) 对于连通图g ，等号成立当且仅当g 正则图 8 硕l 学位论足 ， 引理2 o 1 3 3 2 ，叫设图g 有n 点、m 条边和个三角形其顶点度序列为 d l ，如，厶令靠= ：1 砖，( 后= o ，1 ，) 表示q - 谱中的肛谱距，那么 由引理2 0 1 3 可以得到下面推论： 推论2 0 1 4 设图g 和g ，关于q 矩阵同谱，那么 ( 1 ) g 和g ，有相同的顶点数； ( 2 ) g 和g ，有相同的边数； ( 3 ) g 和g 7 的顶点度序列的平方和相等 引理2 0 1 5 3 2 1 如果两个图q 同谱，那么它们必定c 同谶 引理2 o 1 6 1 1 设社是图g 的一个顶点，( 铭) 是与珏邻接的所有点的集 合，e ) 是包含点u 的所有圈的集合，那么g 的特征多项式满足： r ( g ) ( a ) = a r ( g u ) ( a ) 一r ( g u v ) ( a ) 一2 以( g y ( z ) ) ( 入) 口( u )z c ( u ) 引理2 0 1 7 删设图g 有礼2 个顶点，g ，= g + e ，那么 魄( g ，) l ( g ) 沈( g ，) 沈( g ) ( g 7 ) 2 ( g ) ， 其中g ，= g + e 由图g 插入一条新边e 而得 引理2 0 1 8 泓，删设图g 有礼2 个顶点，则西+ l p l d l + 如其中，d 1 是g 中的最大顶点度，如是g 中的次大顶点度，p l 是g 的最大l a p l a c i a i l 特征 值 引理2 0 1 9 3 设连通图g 有礼3 个顶点，那么化d 2 ，其中如是g 中 的次大顶点度，助是g 的次大l a p l a u c i a n 特征值 引理2 0 2 0 删设简单图g 有n 个顶点，则 m g ( n ) 引去 其中仇g ( 佗) 是l a p a l c i a n 特征值礼的重数，d l 是g 中的最大顶点度，如是g 中 的最小顶点度，【z j 表示不小于z 的最大整数 9 霹 n 汹 + 霹 n 汹 3 +吼 | l 乃 砖 n：i m 2 | | 易m 2 i i 或 n ! l = 噩 n i i l 譬l 的i 誓确定问题研究的若十结采 关于一个图和它的补图的l a p l a u c i a n 谱的关系有如下结论 引理2 o 2 1 例设否表示图g 的补图，设p 1 p 2 2p n ( = o ) 和 面1 面22 瓦( = o ) 分别是g 和召的l a p l a c i a n 谱，则地+ 面n = n ( 蕾 l ，2 ，钆一1 ) ) 因为丽= 召+ 6 ，所以由引理2 o 2 1 可得下面引理 引理2 o 2 2 设p l i “2 i “n ( = o ) 是图g 的l a p l a c i a n 谱，那么 n + l p l + 1 p 2 + 1 一1 + 1 p n ( = o ) 是图g 6 的l a p l a c i a n 谱 引理2 0 2 3 川双星图由它的l a p a l c i a n 谱确定 引理2 o 2 4 如图2 1 所示，似双星图风( p ，q ) q 1 ) 由它的l a p a l c i a n 谱确定 文) g 图2 1 似双星图凰仞，g ) 白g 1 ) 引理2 o 2 5 4 1 设t 是竹个顶点的树，c ( 丁) 是它的线图那么胁( t ) 九( 三( r ) ) + 2 ，其中i = 1 ，2 ，扎 硕卜学位论文 第3 章l o l l i p o p 图的谱确定问题 首先介绍一下l o l l i p o p 图的定义圈图q 上任意一点与路图r p 的一个悬挂 点之间添加一条边，便得到了l o l l i p o p 图( 见 4 2 】) ，记为巩 p 显然，它是一个具 有n 个顶点和n 条边的单圈图若把孤立点看成是r ，圈q 和这个点之间添加 一条边，即得到图+ 1 p ，如图3 1 所示若把圈q 分别添加到路图忍和r 上， 即得到图2 ，p 和风p ，亦如图3 1 所示一 丑| 卅1 巾2 ，p u n p 一1 u n p 玩p 图3 1l o l l i p o p 图 3 1 图巩，p ( p 是正奇数) 由它的邻接谱确定 下面，先来计算图，p 的邻接特征多项式 对于图l p ，由引理2 o 1 得 尸( + 。，p ) ( a ) = 入户( g ) ( a ) 一f _ ( 昂一，) ( a ) 假设口1 ，6 1 是多项式r ( 雌+ 1 ，) ( a ) 的系数，那么 口l = a ；6 1 = 一1 对于图2 p ，由引理2 o 1 得 兄( 炜+ 2 ，p ) ( a ) = 入死( ，p ) ( 入) 一p a ( 岛) ( 入) = a ( a r ( q ) ( a ) 一r ( 昂一。) ( a ) ) 一尸a ( g ) ( a ) = ( r 一1 ) 以( q ) ( a ) 一a n ( 昂一。) ( a ) | ! | i 的谱确定问题研究的若干结果 假设a 2 ，6 2 是多项式r ( ：，p ) ( 入) 的系数，那么 f 口2 ：a a l 一1 ：入2 1 ， 【6 2 = 一g 1 = 一入 对于图+ 3 ，p ，由引理2 0 1 得 p a ( 坼+ 3 ，p ) ( 入) = 入p a ( h p + 2 p ) ( 入) 一r a 1 ( 日) 入2 ( 巩，p ) 口 注3 1 3 引理3 1 2 也可以由巩，p 的邻接特征多项式得出 定理3 1 4 图巩，p ( p 是正奇数) 由它的邻接谱确定 证明设图g 与= 风，p ( p 是j 下奇数) 关于邻接矩阵同谱，则g 和有相 同的点数跟边数另外，和g 有相同的长度为七( 七任意) 的闭回路定义这个 闭回路为一个七环( 记住，由定义，一个闭回路有固定的方向，并且起止点是同一 个点) 由引理3 1 2 ，图g 的第二大邻接特征值严格小于2 如果g 是不连通的， 由引理2 0 ：4 知，只能存在一部分具有一个邻接特征值2 因此，图g 中存在一 个圈下面，我们通过乏( 1 i n p ) 做递推，证明图g 是由一个l o l l i p o p 图 ，p 替换其悬挂点为定点数为n p 一主+ 1 的图得到的也就是说，当i = 佗一p 时，这就意味着g 与同构 情形蕾= 1 我们知道，g 没有舡环( 七 a 1 ( h ) a 2 ( 珥，p ) 口 显然，以，p 与风，p 的差异不大定理3 1 4 的证明方法同样适用于图磁，p ( p 是正奇数) 对于i n 一2 ，递推讨论类似与定理3 1 4 ，只是在最后一步讨论顶点 钞的度为3 即可这样便得到下面的定理 定理3 1 6 图磁p ( p 为正奇数) 由它的邻接谱确定 当p 为正偶数时，上面的证明方法不可取对于l o l l i p o p 图巩 p ( p 为正偶数) 来说，我们没有找到邻接同谱对但是，对于图以，p 来说，有下面的反例 定理3 1 7 如图3 2 所示，图弼6 和图g 7 关于邻接矩阵同谱；它们的补图也 关于邻接矩阵同谱 图3 2 同谱图丑5 ，6 和g 7 证明考虑图蟛6 中的四个黑色顶点，我们发现每一个白色顶点都有两个或者 零个黑色邻居顶点对于每一个有两个黑色顶点的白色顶点口，删掉口与它的邻居 顶点之问的边，并在 和其它两个黑色顶点之间添加边这样，图塌6 就变成了 1 6 硕卜学位论文 g ，g o d s i l 和m c k a y ( 见 4 3 】或【7 1 ) 已经证明了这种转换保持邻接谱不变及其补 图的邻接谱不变( 在 7 】中，这种转换称为g o d s i l - m c k a y 转换，见引理2 o 7 ) 口 显然，焉，6 和g ，不同构那么，弼，6 不能由它的邻接谱确定，因为塌，6 和g ， 的补图也是同谱的，所以蟛，6 关于所有的广义邻接矩阵( 见【7 】) 都不能谱确定 推论3 1 8 俄6 关于所有的广义邻接矩阵都不能谱确定 注3 1 91 、a y f b h - r z a i e ( 交流) 指出，通过计算l o l l i p o p 图中的长度为4 的闭 回路的数目，可以证明玩，p ( p 为大于等于6 的偶数) 由它的邻接谱确定但是 l o l l i p o p 图巩4 是否可以由它的邻接谱确定仍未能解决 3 2 图风，p 由它的l a p l a c i a n 谱确定 下面直接给出证明过程 定理3 2 1 图月p 由它的l 印l a c i a n 谱确定 证明假设图g 和风，p 关于l a p l a c i a n 矩阵同谱，那么g 有扎顶点由2 0 5 知，图g 和风，p 由相同的l a p l a u c i a n 特征多项式，且g 和巩，p 有相同数目的边 和生成树数目运用引理2 0 6 知4 p 1 4 8 那么g 的顶点最大度小于等于3 同时，由2 o 5 可得? 衙= ? 哿，其中吨，分别是图g 和风，p 中的顶点 度假设g 中存在z 个顶点度为1 的点，可个顶点度为2 的点，z 个顶点度为3 的 点，则 解方程组( 3 2 1 ) 得z = 1 ，箩= n 一2 ，z = 1 那么g 必存在一个圈，即g 必为一个 l o l l i p o p 图，设为风，d ( 8 是未知数) 下面，我们来确定口计算图巩，p 中的生成 树的数目，总共有p 棵生成树由于g 和风，p 有相同数目的生成树，而且生成树 的数目取决于圈q 的长度，则n = p 所以g 与鼠，p 同构口 对一个图而言，它的l a p l a c i a l l 特征值决定了它的补图的l a p l a c i a n 特征值忸4 1 ， 于是得到下面的推论 推论3 2 2 玩补图由它的l a p l 撕a n 谱确定 1 7 l2 3 ，f 、l ， 2 一 n4+1 + 2 9 配 = 眙 + o + 秒 y 2 秒 4 + + + z z z 、-lii-，、ll【 图的谱确定问题研究的若干结果 3 3 图 p 由它的q 一谱确定 下面，我们用( g ) 来表示图g 的第二大q 一特征值 引理3 3 1 对任意