（基础数学专业论文）由图的谱和角确定的问题.pdf

摘要 一个图是谱确定的，简单地说是指，任何与它不同构的图必定和它具 有不同的谱目前对谱确定问题的研究结果( 包括寻找同谱对) 并不多， 半个世界以来，出现了一些用邻接谱和l a p l a c i a n 谱来刻画一些特殊结构 图的文章，以及少量用特征值和角共同刻画一些特殊图的文章在前人的 基础上，本文通过计算图的邻接特征多项式，闭路数目，利用二部图同 l a p l a c i a n 谱必l i n e 一同谱的性质，以及有相同特征值和角的图的一些特 点来研究一些特殊结构的非正则图的谱( 和角) 确定问题，得到了如下一 些结论： ( 1 ) 两个不同构的c 。，n 。阳，m 图没有相同的邻接谱 ( 2 ) 图s 1 , 1 , 1 , 2 1 + 1 不能由邻接谱确定，其中2 1 ( 3 ) 两个不同构的图q ， 没有相同的邻接谱 ( 4 ) 冠图go 虬可由其l a p l a c i a n 谱确定，其中n 为偶数 ( 5 ) 图舢可由其l a p l a c i a n 谱确定，其中m 为偶数 ( 6 ) 冠图go 研可由其特征值和角确定 ( 7 ) 图，p ，。可由其特征值和角确定，其中m 为奇数 ( 8 ) 单轮图+ 。可由其特征值和角确定 ( 9 ) 树l 可由其特征值和角确定 ( 1 0 ) 图，即可由其特征值和角确定，其中m 为奇数 ( 1 1 ) 冠图r ok t ，饱和烷烃分子g 也。+ z 的分子图可由其特征值和角 确定 关键词：邻接矩阵，l a p l a c i a n 矩阵，特征值，邻接谱，l a p l a c i a n 谱，同谱图，角， 顶点度对，冠图 i i a b s t r a c t ag r a p hi ss a i dt ob 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 oo 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 n l es p e c t r u m a n s w e r i n gt h i sp r o b l e ms e e m so u to f r e s e a r c h ( i n c l u d i n gf i n d i n gc o s p e c t r a lg r a p h s ) ，n o w a tt h eb a s i so ft h e m ，i nt h i s p a p e r ，b yc a l c u l a t i n ga d j a c e n c yc h a r a c t e r i s t i cp o l y n o m i a l ，t h en u m b e ro fd o s e d - c i r c u i t ，u s i n gt h ep r o p e r t yt h a tb i p a r t i t eg r a p h sw i t hs a m el a p l a c i a ns p e c t r u m m u s tb el i n e - c o s p e c t r a la n dt h ep r o p e r t yo fg r a p h sw i t ht h es a m ee i g e n v a l u e sa n d a n g l e st os t u d ys o m en o n r e g u l a rg r a p h sw i t hs p e c i a ls t r u c t u r e w ep r o v et h a t ： ( 1 ) n og r a p h sg l m ，n 3 ，批8 , r ec o s p e c t r a l ( 2 ) g r a p h ss 1 ，1 ，1 ，雹+ l 谢t h 之n o te q u a l1i s n td e t e r m i n e db yi t sa d j a c e n c ys p e c - t r u m ( 3 ) n og r a p h sq g ，sa r ec o s p e c t r a l ( 4 ) t h ec o r o n ao fqa n d 厩w i t hne v e ni sd e t e r m i n e db yt h e i rl a p l a c i a n s p e c t r u m ( 5 ) g r a p hz k p l 口w i t hme v e ni 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 ) t h ec o r o n ao fq a n dk 1i sc h a r a c t e r i z e db ye i g e n v a l u e sa n da n g e l s ( 7 ) g r a p h p ，g w i t hm o d di sc h a r a c t e r i z e db ye i g e n v a l u e sa n da n g e l s ( 8 ) s i n g l ew h e e lg r a p h + 1i sc h a r a c t e r i z e db ye i g e n v a l u e sa n da n g e l s ( 9 ) t h et r e e 死i sc h a r a c t e r i z e db ye i g e n v a l u e sa n da n g e l s ( 1 0 ) g r a p hc k sw i t hpo d di sc h a r a c t e r i z e db ye i g e n v a l u e sa n da n g e l s ( 1 1 ) t h ec o r o n ao fr a n dka n dak i n do fm o l e c u l a rg r a p ho fa n ( y la r ec h a r - a c t e r i z e db ye i g e n v a l u e sa n da n g e l s i i i k e y w o r d s ：a d j a c e n c ym a t r i x ，l a p l a c i a nm a t r i x ，e i g e n v a l u e 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 ，c o s p e c t r a l ，a n g e l ，v e r t e xd e g r e ep a i r ，c o r o n a i v 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的研究成果除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明本人完全意识 到本声明的法律后果由本人承担 学位论文作者签名：参f 翼肇劲1 年6 月7 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了饵学校有关保留、使用学位论文的规定，研究 生在校攻读学位期间论文工作的知识产权属湖南师范大学，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅本人授权湖南师范大学可以将学位论文的全部或部分内容编 人有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文 本学位论文属于 1 、保密口，在 年解密后适用本授权书 2 、不保密瓯 ( 请在以上相应方框内打“、 ) 日期：研年6 月7 日 醐叩石月尸日 苓一翠jf 蓼壤 j d刘v苌 名 名 签 签 者 师 作 导 由图的谱( 和角) 确定的问题 1 绪论 1 1 谱确定及相关问题的研究背景 图的谱确定问题是图论中的一个重要问题，主要涉及图的邻接谱与图 的l a p l a c i a n 谱的研究，其研究的主要途径是通过图的矩阵( 邻接矩阵或 l a p l a c i a n 矩阵) 表示，建立图的拓扑结构( 特别是图的各种不变量) 和图的 矩阵表示的置换相似不变量之间的联系，通过矩阵论，以及组合矩阵论中 的经典结论，用于图的拓扑结构的研究 1 9 5 6 年，g f i n t h a r d 和阶i m 口s 在一篇把图谱理论与化学中h f i c k e l 7 s 理论 相联系的论文 7 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 r 1 1 】在考虑k a c 1 7 1 提出的问题：“一个人 能否听到鼓声的形状? ”时用一个图模拟了鼓声的形状，这样，鼓声就可以 用图的特征值刻画 所谓图的“谱确定问题”，简单地说是指，根据已有的特征值是否可以 确定出唯一的图，如果存在两个或者更多的图具有一样的谱，那么这些图 便是同谱图所以，寻找同谱图也是谱确定问题的范畴自1 9 6 7 年后，许 多同谱图的例子已经找到，其中令人惊奇的结论是：s c h w e n k 2 6 在1 9 7 3 年 声明几乎所有的树都不能由它们的邻接谱确定后来，g o d s i l 和m c k a y 证 明了几乎所有树的补图都不能由它们的邻接谱确定m c k a y 还证明了几乎 所有的树都不能由它们的l a p l a c i a n 谱确定【2 3 】在这些结论后，关于一般 的图是否由它们的谱确定的问题就没有统一的结论几乎所有的图都由 它的谱确定? 还是几乎所有的图都不能由它们的谱确定? 或者二者都不 是? 迄今为止，我们知道扎个顶点的已知的非谱确定图的比例远远大于已 知的谱确定图的比例，但当礼叶o o 时这两个比例都趋于零计算机的计 硕士学位论文 算结果表明大部分1 1 个顶点( 或更少的顶点) 的图是谱确定图，但是，当n 逐渐变大时，计算机很难运算出结论 对于那些不能谱确定的图形，为了更好地刻画它的特征，还引入了一 个新的变量一角，这在 s l 中有较多的介组 1 2 概念与记号 本论文只研究简单无向图，设g = ( y ( g ) ，e ( g ) ) 是一个简单无向图，其 点集和边集分别是v ( a ) 和e ( g ) ，对任意的 v 点 的度表示为也，图 g 的顶点度序列记为d 。d 2 d n ，记最大度= d l ，最小度6 = 如 ，r 图g 的邻接矩阵定义为a ( g ) ：( 口幻) ，这里o ；j ： 二 ? “? ，矩阵 l u o 和3 l ( g ) = d ( g ) 一a ( g ) 称为图g 的l a p l a c i a n 矩阵，其中d ( g ) 是n x 他的顶点 度对角矩降多项式r ( g ) ( a ) = d e t ( m a ( g ) ) ( 或兄( g ) ( 肛) = d e t ( m l ( g ) ) ， 定义为g 的邻接特征多项式( 或l a p l a c i a n 特征多项式) ，其中，是单位矩 阵，设入1 入2 a n ，p 1 p 2 脚( = 0 ) 分别是图g 的邻接特征 值，l a p l a c i a n 特征值图g 的邻接谱( 或l a p l a c i a n 谱) 分别由图g 的邻接 特征值( 或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 和g 具有相同的邻接谱( 或l a p l a c i a n 谱) ，并且日和g 不同构，则图日称为图g 的邻接同谱对( 或l a p l a c i a n 同谱对) 图1 - 1 和图 1 - 2 分别给出了一对邻接同谱图和一对l a p l a c i a n 同谱图 a 1 1 如果两个图 的线图关于邻接矩阵同谱，那么这两个图称为l i n e - 同谱；如果树t 中某 个顶点 的度大于或等于3 ，则称口为大顶点 给定两个图g 。和g ：，图g 称为g t 和g 。的不相交的并( 或和) ，记为 g = g 1 + g 2 ，若v ( a ) = y ( a 1 ) uv ( a 2 ) 和e ( c ) = e ( g i ) ue ( g 2 ) 2 由图的谱( 和角) 确定的问题 图1 - 1 邻接同谱对图1 - 2l a p l a c i a n 同谱对 下面给出角的定义：设u 1 u 2 是a 的特征值入l 入2 入n 中的所有不同值，并设 e 。，e 2 ，e n ) 为彤的一组标准正交基，邻接矩 阵a 有谱分解a = v l r + 忱b + + p m ，只指从舻到特征空间e ( v t ) 的正 交映射( 其中砰= 只= p s ；i = 1 ，m ；只弓= 0 ，i j ) o t i i = c d s 如( 其中岛 是e ( v i ) 与e 1 之间的角，a o 0 ) 称为g 的角，且q 巧= l i p i e j l l ，o i l ，o t i 2 ，q i n 是第i 个特征值角序列，q u ，o t 2 j ，q 叮是第j 个顶点角序列，a 的角矩阵 定义如下：a = 0 q 巧l l m 。，角矩阵是一个图变量如果一个图不变量( 或参 数) 能由特征值和角确定，则称此不变量或参数是e a 一可重构的接下来 给出顶点度对的定义：若移是图g 的一个顶点，d t 是顶点口的度，e 是顶 点u 的所有邻域的度之和，则称( 也，e ) 为顶点口的度对对于角的更多性 质可参考【5 】 1 3谱确定及相关问题的研究现状 下面列举出谱确定问题中一些由邻接谱，l a p l a c i a n 谱或者由特征值和 角共同确定的已有结果 1 k 个不相交的完全图的并，+ ：+ + 。由它的邻接谱确定i s l 2 k 个不相交的路图的并p m 。+ p m 2 + + p m 。，k 个不相交的圈g ，+ g ：+ + g 。的并既能由它们的邻接谱确定，又能由它们的l a p l a c i a n 谱确 定【3 l i 。其中m 2 ，t i 3 ( i = 1 ，2 ，k ) 3 k 个不相交的阶为l 的完全图的并k k t ，线图l ( k n ) ( n 8 ) 和线图 3 硕士学位论文 l ( ，。) ( m 4 ) 及它们的补图，阶为( 3 ，6 ) 的广义四边形的点图等既能由 它们的邻接谱确定，又能由它们的l a p l a c i a n 谱确定【3 4 正则图中，t 个完全相同的强正则谱确定图的不相交的并，c 5 以， i o ( m ，m 一1 ，m 一2 ) 以，既能由它们的邻接谱确定，又能由它们的l a p l a c i a n 谱确定【3 1 1 5 l o l l i p o p 既由它们的邻接谱确定，又由它们的l a p l a c i a n 谱确定 1 4 1 ，【3 】 6 若二部图g 有三个不同的特征值a 。，a ：，a 。，重数分别为m 。，m 2 ，m 。， 则a 3 = 一a ，a 2 = 0 ，m 3 = r r t l ，g 是m - 个完全二部图纸 的直和，且有 t t 2 一詈( n + s t 一2 ) 个孤立点，这里 i s 产增，i = 1 ，2 ，m 1 进一步，若图 g 是上述图且碍= p , p 是素整数，则g 由它的邻接谱确定i s ) 7 具有三个邻接特征值且最小特征值为一2 的非正则图中有5 个能由 邻接谱确定【3 2 j 8 正则完全多部图既能由它们的邻接谱确定，又能由它们的l a p l a c i a n 谱确定【1 0 j 【1 9 1 9 路的补图由邻接谱确定1 9 1 1 0 图磊由它们的邻接谱确定，图磊的k 个不相交的并 ，+ z m 2 + + 。由它们的邻接谱确定，其中m ；2 ( i = 1 ，2 ，七) 矧 1 1 没有两棵不同构的似星型树同谱( 2 0 1 1 2 t 型树t ( 1 l ，1 2 ，f 3 ) 能由它的邻接谱确定，其中( 1 1 ，2 2 ，f 3 ) ( i ，1 ，2 1 2 ) ， 且l 2 为整数【3 3 】 1 3 所有最大特征值不大于、2 + 锯的连通图由其邻接谱确定【捌 1 4 设g = 乙，+ 历。+ + + t 1 丑+ 2 乃+ 如忍的邻接谱半径a l 2 ，那 么g 由它们的邻接谱确定当且仅当g 中不含这样的部分：它们的不相交 4 由图的谱( 和角) 确定的问题 的并的谱等于反( i = 1 ，4 ) t 2 4 l 1 5 h a m m i n g 图h ( 3 ，g ) ( g 3 6 ) 由邻接谱确定【l 】 1 6 图，瓦，七磊由它们的l a p l a c i a n 谱确定m 1 7 设g = z j l + z j 2 + + 苏+ t i t l + t 2 t 2 + t 3 t 3 的邻接谱半径a l p 1 ( g ( 七+ 1 ，z 一1 ) ) 引理2 7 1 7 1 增大非负矩阵a 的任一元素，a 的最大特征值不会减小j 如 果a 是不可约矩阵，则增大a 的元素，a 的最大特征值会严格增大 引理2 8 1 1 9 1p ，设图g 有n 个顶点和m 条边，令d = ( d 1 ，d 2 ，厶) 是它 的不增度序列，则兄( g ) ( p ) 中的一些系数为 q o = 1 ；q l = 一2 m ；q 2 = 2 m 2 一m 一互1 竺1d i 2 ； q 3 = ( 一4 m 3 + 6 m 2 + 3 m ：1 霹一ld 3 3 ：1 霹+ t r ( a 3 ) ) ， 一1 = - 1 舻1 礼s ( g ) ；q n = 0 俐从图g 的l a p l a c i a n 谱，可以得到： 俐图g 的连通分支数j 俐图g 的生成树的数目 弓l 理2 9 1 1 9 1 ，【2 1 】设图g 中，v ( a ) d ，e ( g ) d ，见l | ( g ) + 1 p l a 。( s ) ，此时日与s 不 同谱，矛盾! 当有两个最大度a ( h ) = 3 时，日可能的图为胁，风，但是a ，( h 7 ) = 2 0 5 2 8 8 a l ( s ) ，a l ( 风) = 2 口2 ，此时右边最高项为一2 t 学，所以p 1 = p 2 ，9 1 = q 2 ( 3 - 6 ) ( 3 - 7 ) 由图的谱( 和角) 确定的问题 此时g 。与g 2 同构 ( 2 ) 当p 1 ：9 1 时，( 3 7 ) 式左边最高项为一4 t 学 若船 9 2 ，则右边最高项为一2 t 掣，矛盾! 所以p 2 = ( 2 ，得到p 1 = p 2 ，q l = q 2 此时g 。与g z 同构 情形2 ：当5 2 时，先计算q 岛。的特征多项式，( 下将其简记为g ) ，反 复利用引理2 2 ，并记p + 口+ s = n 得： ( g ，a ) = ( q ) 驴( 日q + 。，g ) 一妒( 弓一) 妒( + 8 - 1 ，口) 再利用引理2 3 及【1 2 】的结果整理后代入得： ( g ；t + t i 1 ) ( 1 一t 2 )( 暑+ t 一暑一2 ) 【t 一半( 1 2 t + t q 一2 t + 2 t 警) + t 字( t 2 2 t + 2 t j 产+ t q + 2 2 t _ 皆) ) 一挚- i 一学( 1 2 t + t q 一2 t 墨+ 2 亡z 笋) + t 半( t 2 2 t + 2 t 鼍笋+ 一q + 2 2 t 鼍笋) ) ( t 暑+ t 一羞一2 ) t 一- 峙- t 2 + ( i 一2 t + t q 一2 t s 2 + 2 t 孚) + ( t 墨+ 一呈一2 ) t 字( t 2 2 t + 2 t j 乒+ t - q + 2 2 t j 乒) 一二坚军尘( 1 2 t + t q 一2 t 墨+ 2 t 字) 一三二兰掣( 2 2 t + 2 z j 芦+ 一q + 2 2 舌鼍芦) = ( 1 2 t + t q 一2 t 兰+ 2 t 警) ( 卫习= 三+ t 一号一2 t 一半 一t p + 兰+ 萼 ) + ( t 2 2 t + 2 t 二乒+ t 一口+ 2 2 t 二：拳) ( t 鼍 + t 半一2 t 啦2 一鱼t - 1 + 喾) 硕士学位论文 于是，咖( g ；t + t 一 ) ( 1 一t 2 ) ( t 1 ) = ( 1 2 t + t q 一2 墨+ 2 半) ( t 甲+ 一号一2 t j 产) ( t 一1 ) 一矿1 一号+ t 1 一号) + ( t 2 2 t + 2 j 乒+ t q + 2 2 t j 乒) ( t 詈+ t 1 气= 2 2 t 字) ( t 一1 ) 一号+ t 半) = ( 1 2 t ) ( 2 t 1 一号一z 一号) + ( t 2 2 t ) ( t 暑+ 1 2 号) + ( 1 2 t ) ( 一2 生产一芈 + 2 亡鼍产) + ( t 。一2 墨+ 2 t 墨+ 1 ) ( 2 t 1 一号一t 一号) + ( t q 一2 t 墨+ 2 t 墨+ 1 ) ( 一2 t 呈= 产一 t 半+ 2 t 二5 产) + ( t 2 2 t ) ( 亡华+ 1 2 t 字+ 1 + 2 t 字) + ( 2 t 一墨+ 1 + t 一口+ 2 2 t 一墨+ 2 ) ( t 詈+ 1 2 z 号) + ( 2 t 一墨+ 1 + t 一口十2 2 t 一墨+ 2 ) ( t 午+ 1 2 t 字+ 1 + 2 t 字) = ( 1 2 t ) ( 2 t 1 一号一t 一号) + ( t 2 2 ) ( t 号+ 1 2 t 号) + 4 t 3 + 暑一1 2 t 2 + 考十1 2 t 1 + 暑一4 t 量 一t 罟一t 一6 警+ 1 一字+ 2 z 孚+ 6 孚+ 2 + 2 卫鼍卫+ 1 + 2 t q + 1 一号一t q 一号 + 2 z 墨一号+ 4 t + 2 一号一6 旦专苎+ 1 + 2 字+ 2 警一2 1 + 孚+ t 牛棚一2 t 字+ 3 + 6 亡字+ 2 2 午+ 2 + 6 亡詈一墨+ 2 4 t 詈一+ l 一6 t + 1 一詈+ t 詈一q + 3 2 t 詈一q + 2 2 亡号一；+ 3 + 2 亡2 + 竽+ 亡甲+ 3 4 3 + 孚 ( 孓8 ) 设g 1 = q 。舭。与g 2 = 舰。同谱，且p 1 9 1 ，p 2 q 2 ， 由( g 1 ；t 百1 + 一互1 ) = 咖( g 2 ； + t 一) 得， ( g 1 ； + t 一 ) ( 1 一2 ) ( 亡一1 ) = 砂( g 2 ；+ z 一 ) ( 1 一t 2 ) ( 亡一1 ) 分别以p - ，q 1 与p 。，q 2 代入( 3 8 ) 的右端，则相应的右端相等，分别记作 。与妒2 ， 去掉。与砂7 ：中的公共部分后，等式两端仍记为妒7 。= 7 ： ( 1 ) 当q 1 = p 1 时，经比较l 中的最高项为一4 t 罟一等+ 3 若q 2 p 2 ，则2 中的最高项为一2 謦+ 号+ 3 ，矛盾! t 口n 于是q 2 = p 2 ，义p 1 + 9 1 + s = p 2 + 9 2 + s ， 所以p l = p 2 ，9 1 = q 2 2 0 由图的谱( 和角) 确定的问题 此时g ，与g 2 同构 ( 2 ) 当q l p 1 时，经比较l 中的最高项为一2 t 謦+ 暑+ 3 若q 2 = p 。，则2 中的最高项为一4 携一警 ，矛盾! 所以q 2 p 2 ，此时2 中的最高项为一2 警+ 差+ 3 可得p t = p 2 ，9 1 = q 2 ， 于是g 。与g z 同构 3 4 冠图go ( 1 由l a p l a c i a n 谱确定，其中n 为偶数 先给出冠图n c ok 1 的定义：它由圈图q 上的每一个顶点分别与 个只相连而得到，亦如下图所示： 图3 - 7 定理3 4 冠图ok l 由l a p l a c i a n 谱确定，其中n 为偶数 证明：假设图g 与go 关于l a p l a c i a n 矩阵同谱，那么g 有加个顶点， 由引理2 8 知，图g 与go 甄有相同的l a p l a c i a n 特征多项式，相同的边数 和生成树数目以及连通分支数目， 因为go 甄连通分支数为1 ，边数为2 船，所以g 为连通的单圈图， 又g ok 1 的生成树数目为n ，于是g 的生成数数目为佗，所以g 所含 2 1 硕士学位论文 圈的圈长为m 运用引理2 8 知：銎。霹= 鍪。云2 ，其中d i ，玉分别是图g 与图go 虬 中的顶点仇的度， 运用引理2 9 知，4 u l ( c ok 1 ) 5 ， 那么g 的最大度小于等于4 ，假设g 中存在z 个顶点度为1 的点，y 个 顶点度为2 的点，z 个顶点度为3 的点，w 个顶点度为4 的点，则 i z + 2 + 3 z + 4 w = 4 n ( 3 - 9 ) z 十y + z + w = 2 n ( 3 - 1 0 ) iz + 4 y + 9 z + 1 6 w = 1 0 n ( 3 - 1 1 ) 当n 为偶数时，g 与go 致均为二部图，由它们的l a p l a c i a n 矩阵同谱 以及引理2 1 0 知，g 的线图l i n e ( g ) 与qo 甄的线图l i n e ( c o1 ( 1 ) 的邻接 矩阵同谱所以，l i n e ( g ) 与l i n e ( c o ) 中所含三角形个数相等于是， 几( 三) = z ( 兰) + 叫( 三) 得到1 , = z + 4 w( 3 - 1 2 ) f z = m 由( 3 - 0 ) ，( 3 - 1 0 ) ，( 3 - 1 1 ) ，( 3 - 1 2 ) 得 可_ 0 忙鼍 因此g 与go 所同构证毕 对一个图而言，它的l a p l a c i a n 特征值决定了它的补图的特征值。于 是得到下面的推论 推论3 4 冠图q ok ，的补图由l a p l a c i a n 谱确定，其中几为偶数。 3 5 图，舢由l a p l a c i a n 谱确定，其中m 为偶数 2 2 由图的谱( 和角) 确定的问题 首先给出图藏g 的定义：它指由圈图上的一个顶点 与两条顶 点数分别为p ，q 的路弓以及岛的一个悬挂点分别相连而得到的图，亦如 下图所示： 图3 _ 8 2 定理3 5 图日m 舢由l a p l a c i a n 谱确定，其中m 为偶数 气 证明：设n = m + p + q ，假设图g 与 p 口关于l a p l a c i a n 矩阵同谱f 那么g 有n 个顶点，由引理2 8 知，g 与删有相同的特征多项式，相 同的边数和生成树数目以及连通分支数目。与定理3 4 的证明类似：可证 得g 为连通的单圈图，且圈长为m ，运用引理2 9 得 5 p ，则q 1 q ，由引理2 6 知： a ( g ) = a l ( ，p 。，口1 ) 入1 ( ，m ) ，矛盾! 因此p 1 = p ，q 1 = q ， 此时g 和如，加同构 口 ( 3 - 1 6 ) 由图的谱( 和角) 确定的问题 4 几类特殊图的特征值和角确定问题 4 1 冠图go ( 1 由特征值和角确定 定理4 1 冠图go 甄由特征值和角确定 证明：假设图g 和q 。有相同的特征值和角q 巧， ( i = 1 ，m ；j = 1 ，2 n ) ， 则由引理2 1 3 ，2 1 4 知图的连通与否是e a 一可重构的，是否为单圈图 亦是e a 一可重构的， 因为g ok 。是连通的单圈图，所以g 也是连通的单圈图设g 所含 圈的圈长为8 ，下面就礼的奇偶性分两种情形讨论： 情形1 ：当n 为奇数时，图g ok a 非二部图 若s 为偶数，则g 为二部图，矛盾! 所以s 为奇数。 若n s ，则go 甄中长为s 的闭路数目为0 ，而g 中长为s 的闭路数 目为l ，由引理2 4 知，如果两个图的邻接特征值相同，则它们含有相同的 任意长度的闭路数目，矛盾! 若n s ，必n s 2 ，则g 必包含图g ，作为子图( 见下图4 1 ) 图4 - 1 由 2 】知：印e c ( gok x ) = 卜士v 1 一c o s 2 誓+ 1 “c d 舡节“即，士厣) 所以，a l ( g ok 1 ) = 1 + 以= a 1 ( g o 研) ， 而入1 ( go 所) 3 ， 则x 的顶点度对为 ( 1 ，4 ) ，( 1 ，4 ) ，( 4 ，7 ) ，( 4 ，7 ) ，( 4 ，1 0 ) ，( 4 ，1 0 ) 】， _ l _ - _ - _ 、j _ _ _ - l _ l ，、_ _ _ l l _ - _ o 、j - _ i _ l _ l i _ ， 2 m + 2m - - 2 设图x 与图x 有相同的特征值和角，则x 7 有m 个4 度顶点，2 m + 2 个悬挂顶息如果图x 中有一个4 度顶点缸与三个4 度顶点邻接，则u 的顶点度对为( 4 ，n ) ( n 1 3 ) ，矛盾! 所以图x 的每个4 度顶点至多与两个4 度顶点邻接，则x 与图 同构证毕 类似地，我们可以证明下面的图4 - 8 可以由特征值和角确定 图4 8 证明：用y 表示上面的图，假设图y 与图y 有相同的特征值和角与 定理4 5 2 证明类似可得，y 是有仇个3 度顶点，m + 2 个1 度顶点的树若 图y 7 的一个3 度顶点u 与三个3 度顶点邻接，则顶点u 的度对为( 3 ，9 ) 而 图y 的顶点度对序列为【( 1 ，3 ) ，( 1 ，3 ) ，( 3 ，5 ) ，( 3 ，5 ) ，( 3 ，7 ) ，( 3 ，7 ) ) ，故y ， 、- _ - _ 、一一l _ 一、- i i _ - 、一- l _ _ - ， m + 2m 一2 的顶点度对为 ( 1 ，3 ) ，( 1 ，3 ) ，( 3 ，5 ) ，( 3 ，5 ) ，( 3 ，7 ) ，( 3 ，7 ) ，不存在顶点度对 、_ _ _ - i 一、一i l - ，、- _ _ _ l - 、一一_ _ _ _ 一 ，n + 2m - 2 为( 3 ，9 ) ，矛盾! 因此图y 7 的每个3 度顶点至少与一个悬挂点邻接，这就使得y 与y 同构 口 由图的谱( 和角) 确定的问题 结语 本文通过计算图的邻接特征多项式，闭路数目，利用二部图同l a p l a c i a n 谱必l i n e 一同谱的性质，以及有相同特征值和角的图的一些特点来研究 一些特殊结构的非正则图的谱( 和角) 确定问题，得到了一些结论其中 冠图go 研在n 为奇数时以及图，m 在m 为奇数时是否由l a p l a c i a n 谱确定；图，m 和图 ，在m 为偶数时是否由特征值和角确定，仍有 待解决，是本论文的开放性问题，由图的谱( 和角) 确定的问题值得更深 入的探讨 参考文献 【1 】b a n g ，s e r v a nd a m j h k o o l e n s p e c t r a lc h a r a c t e r i z a t i o no ft h e h a m m i n gg r a p h s j 。l i n e a ra l g e b r aa p p l , 2 0 0 8 ，( 4 2 9 ) ：2 6 7 8 - 2 6 8 6 【2 】b a r i k ，s s p a t i b k s a r m a t h es p e c t r u mo ft h ec o r o n ao ft w o g r a p h s j d i s c r e t em a t h ，2 0 0 7 ，( 2 1 ) ：4 7 - 5 6 【3 】b o u l e t ，r b j o u v e t h el o l l i p o pg r a p hi sd e t e r m i n e db yi t ss p e c t r u m 【j 】- t h ee l e c t r o n i cj o u r n a lo fc o m b i n a t o r i c s ，2 0 0 8 ，( 1 5 ) 【4 】b i g g s ，n a l g e b r a i cg r a p ht h e o r y ，s e c o n de d m c a m b r i d g e ：c a m b r i d g e u n i v e r s i t yp r e s s ，1 9 9 3 【5 】c v e t k o v i d ，d p r o w l i s o n s s i m i d e i g e n s p a c e so yg r a p h s 【m 】c a m - b r i d g e ：c a m b r i d g eu n i v e r s i t yp r e s s ，1 9 9 7 ，1 ：7 5 8 5 【6 】c v e t k o v i 6 ，d p r o w l i s o n s s i m i d s i g n l e a sl a p l a c i a n so ff i n i t e g r a p h s j l i n e a ra l g e b r aa p p f j 2 0 0 7 ，( 4 2 3 ) ：1 5 5 - 1 7 1 【7 】c v e t k o v i 6 ，m m d o o b & h s a c h s s p e c t r a lo