（基础数学专业论文）关于图的谱确定问题.pdf

湖南师范大学硕士学位论文 o 1中文摘要 “哪些图由它的谱确定? ”的同题予半个世纪前起源于化学。 1 9 5 6 年g t i n t h a r d 和p r i m a s 在一篇把图谱理论与化学中h t i c k e l s 理论 相联系的论文中提出了该问题。另一个应用来自于1 9 6 6 年f i s h e r 考 虑的k a c 提出的一个问题：“一个人能否听到鼓声的形状? ”他用 一个图模拟了鼓声的形状，那么鼓声就由该图的特征值来刻画了 k a c 的问题实际上也是我f f 丁的问题 目前对该问题特别是“哪些图由它的邻接谱或l a p l a c i a n 谱确定? ” 的研究结果并不多半个世纪以来，出现了一些研究正痢图和特殊 结构图的线图的谱刻画的文章而对于非正则图的研究结果极为少 见本文主要研究一些特殊结构的菲正则图的谱确定同题，得到了 如下一些结论： ( 1 ) 图乙( 一类特殊的似星树) 既能由它的邻接谱确定，又能由它的 l a p l a c i a n 谱确定；进一步，最大邻接特征值小于2 的图既能由它的 邻接谱确定，又能由它的l a p l a c i a n 谱确定 ( 2 ) 图磊的不相交的并乙：+ 乙：+ - + 乙。能由其邻接谱确定，其 中，n 一，都是大于1 的正整数；e 个不相交的图玩的并七磊 能由其l a p l a c i a n 谱确定； ( 3 ) 似星树( 包括星图) 由它的l a p | a c i a n 谱确定； ( 4 ) 梳图由它的l a p | a c t a n 谱确定； ( 5 ) 饱和烷烃分子g 风。+ 。的分子图由它的l a p l a c i a n 谱确定； ( 6 ) 眠和其它两类似双星图虽不能由它们的邻接谱确定，但能由它 们的l a p l a c i a n 谱确定； ( 7 ) 恰有一个l a p l a c i a n 特征值大于3 的树由它的l a p l a c i a n 谱确定； ( 8 ) 恰有两个l a p l a c i a n 特征僮大于2 的树( 包括双星图) 由它的l a p l a - c i a a 谱确定； 湖南师范大学硕士学位论文 i i ( 9 ) 多图l 。( ) 和o ( 风) 由它们的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 谱；同谱图；星图；似星树；梳图；分子图 0 2 a b s t r 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 rs p e c t r a ? ”g o e s b a c kf o rh a l fac e n t u r y ，a n do r i g i n a t e sf r o mc h e m i s t r y i n1 9 5 6 ，g i i n t h a r d a n dp r i m a sr a i s e dt 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 r yo fg r a p h s p e c t r at o h f i c k e st h e o r yf r o mc h e m i s t r y a n o t h e ra p p l i c a t i o nc o n i e sf r o m f i s h e ri n1 9 6 6 ，w h oc o n & 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 es h a p e o fad 1 u r n ? ”h em 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 nt 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 n v a l u e so ft h eg r a p h t h u sk a c s q l m s t i o ni se s s e n t i a l l yo u p $ a n s w e r i n gt h eq u e s t i o nf o ra d j a c e n c yo rl a p l a c i a nm a t r i c e ss e e m so u to f r e s e a r c h i nt h ep a s th a l fc e n t u r y , t h e r ea r em a n yr e s u l t sa b o u tt h eq u e s t i o n f o rr e g u l a rg r a p h sa n ds o m es p e c i a ll i n eg r a p h s b u tf o rn o n r e g u l a rg r a p h s ， t h e r e8 a ef e wa b o u ti t i nt h i sp a p e r w ep r o v et h a t ( 1 ) 乙i sd e t e r m i n e db y i t sa d j a c e n c ys p e c t r u ma sw e l la st h el a p l a c i a ns p e e t r u m f u r t h e r m o r e ，g r a p h sw i t hl a r g e s ta d j a c e n c ye i g e n v a l u el e s st h a n2a r e d e t e r m i n e db yt h e i ra d j a c e n c ys p e c t r aa sw e l la sl a p l a c i a ns p e c t r a ( 2 ) t h ed i s j o i n tu n i o n o f g r a p hz 。1 乙2 ，磊( d e n o t e db y 互、+ 乙。十。+ 五t k ) i sd e t e r m i n e db vi t sa d j a c e n c ys p e c t r u m ，w h e r e a l lt h en u m b e r sn 1 ，7 t 2 ，“k a r ep o s i t i v ei n t e g e rg r e a t e rt h a no n e ；kd i s j o i n tu m o n o fz ni sd e t e r m i n e db y i t sl a p t a c i a ns p e c t r u m ； ( 3 ) s t a r l i k et r e e s ( i n c l u d i n gt h es t a r ) a r ed e t e r m i n e db y t h e i rl a p l a c i a ns p e c - t r a ； ( 4 ) c o m bi sd e t e r m i n e db y i t sl a p l a e i a ns p e c t r u m ； ( 5 ) ak i n do f m o l e c u l a rg r a p ho fa l l ( y li sd e t e r m i n e db y i t sb a p l a c i a n s p e c t r u m ； ( 6 ) g r a p h 眠a n d t h eo t h e rt w od o u b l es t a r l i k eg r a p h sa r en o td e t e r m i n e db y t h e i ra d j a c e n c ys p e c t r a ，b u tt h e ya r ed e t e r m i n e db yt h e i rl a p l a c i a ns p e c t r a ， 湖南师范大学硕士学位论文 i v r e s p e c t i v e l y ； ( 7 ) t r e e sw i t he x a c t l yo n el a p l a c i a ne i g e n v a l u eg r e a t e rt h a n3a r ed e t e r m i n e d b yt h e i rl a p l a c i a ns p e c t r a ，r e s p e c t i v e l y ； ( 8 ) t r e e sw i t he x a c t l yt w ol a p l a c i a ne i g e n v a l u eg r e a t e rt h a n2 ( i n c l u d ed o u b l e s t a rg r a p h s ) a r ed e t e r m i n e db yt h e i rl a p t a c i m ls p e c t r a ，r e s p e c t i v e l y ； ( 9 ) p o l y g r a p h sl 3 ( ) a n dc 4 ( 虬) a r ed e t e r m i n e db yt h e i rl a p l a c i a ns p e c t r a ， r e s p e c t i v e l y k e yw 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 ，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 s t a r ，s t a r l i k et r e e ，d o u b l e s t a r ，p o l y g r a p h 关于图的谱确定问题 o n g r a p h sd e t e r m i n e db y t h e i rs p e c t r u m 本课题受国家自然科学基金似口馏纠和 湖南省教育厅科学研究项目资助( 0 3 8 0 1 9 ) 湖南师范大学硕士学位论文 。1 笫一章 综述 关于“哪些图由它们的谱确定? ”的问题要追溯到半个世纪以 前，起源于化学1 9 5 6 年g f i n t h a r d 和p r i m a s 在一篇把图谱理论 与化学中h i i c k e l s 理论相联系的论文( 见 1 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 ( j 2 d 那时他正考虑 k a c ( 3 1 ) 提出的一个问题：“一个人能否听到鼓声的形状? ”他用一 个图模拟了鼓声的形状，那么鼓声就由该图的特征值来刻画了k a c 的问题实际上也是我们的问题 谱确定问题研究的另一个重要动机来自复杂性理论目前我们 仍不知道图的同构问题是困难闻题还是容易问题由于检查两个图 是否同谱能在多项式时间内完成，那么闻题就集中在检查两个同谱 图是否同构上 自1 9 6 7 年后，许多同谱图的例子已经找到其中最令人惊奇的 结论是s c h w e n k ( 4 ) 在1 9 7 3 年声明：几乎所有的树都不能由它们的邻 接谱确定后来，g o d s i l 和m c k a y ( 5 1 ) 证明了几乎所有树的补图都不 钱由它们的邻接谱确定m c k a y ( 6 ) 还证明了几乎所有的树都不能由 它们的l a p a c i a z i 谱确定在这些结论后，关于一般的图是否由它的 潜确定的问题就没有统一的结论几乎所有的图都由它的谱确定? 还是几乎所有的图都不能由它的谱确定? 或者二者都不是? 迄今为 止，我们知道佗个顶点的已知的非谱确定图的比例远远大于已知的 谱确定图的比例但当n 一。时，这两个比例都趋于零计算机的 计算结果表明大部分1 1 个顶点( 或更少的顶点) 的图是谱确定图 目前问题“哪些图由它的邻接矩阵或l a p l a c i a n 矩阵的特征值确 定? ”的研究结果并不多、证明图是谱确定的并不容易我们用来 证明图的谱确定的工具似乎只能证明某些特殊结构的图，如正则图 等我们对谱确定图知之甚少 1 9 7 0 年，m d o o b 在文献 7 i 中刻画了有少量不同邻接特征值的 图，并有如下结论： ( 1 ) g 有一个特征值当且仅当g 是完全不连通图；g 有两个不同特 征值a 1 2 ，重度分别为m ，和m 2 当且仅当g 是帆个阶为a ，+ 1 的 完全图的直和，此时沁= 一1 ，m 。= m 1 a 。由此可得出完全图和无边 图由它f f j 的邻接谱确定 ( 2 ) 若二部图g 有三个不同的特征值 。，a z ，a 3 ，重度分别为m ，m 。，m 。， 则a 3 = 一a l ，a 2 = 0 ，m 3 = m 1 且g 是m i 个完全二部图赫。，的直和和 t o , 3 一2 1 ( f i + 岛一2 ) 个孤立点，这里7 i 8 ，= a ，i = 1 ，一，m 1 进一步， 若图g 是上述图且a = p ，p 是素整数。则g 由它的邻接谱刻画 有三个特征值的连通正则图是强正则图现在仅知道有少量的 强正则图和它们的补图是谱确定图( 既能由它们的邻接谱确定，又能 由l a p l a c i a n 谱和距离谱确定) ：k 个不相交的阶为f 的完全图的并k k t 和下面所说的线图厶( i ( n ) ( r t 8 ) ，l ( ，。) ( m 4 ) 及它们的补图，阶 为( 3 ，6 ) 的广义四边形的点图( 参见隙表2 ) 等能由谱确定似乎是 强正则图的一个很强的性质绝大多数的强正则图都有与之同谱但 不同构的图 有三个邻接特征值且最小特征值为一2 的非正则图中有5 个能由 邻接谱确定( 见1 9 】9 或1 8 】表6 ) 有三个l a p l a c i a n 特征值的非正则图中 有鸟笼图和另外1 8 个图及其补图由它们的l a p l a c i a n 谱确定f 见f 1 0 1 或【8 】表7 ) 至多有4 个特征值的下列正则图是谱确定图( 8 】) ：( 1 ) it 个 完全相同韵强正则谱确定图的不相交的并及其补图( i i ) g 圆。 及 其补图( i i i ) i g ( m ，m 一1 ，m 一2 ) o 。五及其补图 关于正则图，1 9 6 5 年，h j f i n c k 在文献f 1 1 中有如下结论： 芷则完全多部图由它的邻接谱确定，后来a k k e l n - i a n 证明了更一 般的结论：正则完全多部图由它的l a p l a c i a n 谱确定另外，在文献 中还有一些关于正则图的谱刻画的结论：( 1 ) 对称设计图由它的 邻接谱刻画( 2 ) 度为0 ，1 ，2 ，礼一3 ，n 一2 ，n 一1 的n 阶正则图由它们 的邻接谱刻画，因而也能由它们的l a p l a c i a n 谱确定 有关非正则谱确定图直到2 0 0 2 年，d o o b 和h a e m e r s 用并不容易 的方式证明了路的补图由它的邻接谱确定( 见 1 2 1 ) 而路及其补图很 容易被证明由其l a p l a c i a a 谱确定另外，在综述性文献( 8 】中还有如 湖南师范大学硕士学位论文 3 下有关非正则谱确定图的结论； ( 1 ) k 个不相交的完全图的并。+ 。+ + 。能由它的邻接谱确 定，但不能由它的l a p | a c i a n 谱确定； ( 2 ) 七个不相交的圈的并由它的邻接谱和l a p l a c i a n 谱确定； ( 3 ) 个路图的不相交的并p n 。+ r 。+ + r 。由它的邻接谱和l a p l a c i a n 谱确定 注：如果我们把孤立点看成p 1 ( 一个顶点的路图) ，上面“个不相交的路囝的并能 由它们的邻接谱确定”的结论将是错误的，例如：p - + p 1 与面+ p 3 有相同的邻接谱 ( 图磊h 为任意正整数) 将在第三章中予以定义) 该结论只有当所有的整数n 。、m 都大于1 时才成立为方便，在本文中，我们把孤立点视为- ( 一个顶点的完全d 图) 而 不是p 1 关于线图， 1 】中有结论：三角图( 完全图的线图) 瓦当n 8 时由它的邻接谱确定1 9 5 9 年，s ，s s h r i k h a - l d e 在f 1 3 l 中指出： 当扎4 时，二( ，。) 由它的邻接谱确定后来d o o bi 1 4 1 和c v e t k o v i d 15 】分别独立地推广了这一结论：令g 皇上( ，。) ，m + n 1 8 则当 伽，n ) 2 t 2 + t ，2 t 2 一t 且不存在一个阶为4 t 2 的常量对角的对称 h a d a m a r d 矩阵时，g 由它的邻接谱确定由这个结论可推知：当 m = 2 ，n = 2 或l m n i 一1 时，l ( ，。) 由它的邻接谱确定由于 l ( ) ，三( ，。) 和它们的补图都是强正则图，容易得出它们能由其 l a p l a c i a n 谱确定文献f 8 | 中关于线图的结论有：设g 是连通正则谱 确定图，若g 不是8 个顶点的三连通图，或有卢2 1 个顶点度为n 卢 的正则图，这里o t ，p 都是整数，且。曼 ，则g 的线图l ( g ) 是谱确 定图 另外，还有一些关于平衡不完全区组设计( b i b d ) 的线图的谱刻 画的结论： 1 ( 1 ) 当，a + ) ( 4 ，3 ，2 ) 时，对称b i b d 的线图由它的邻接谱刻画， 当( ，k ，”) = ( 4 ，3 ，2 ) 时，恰有一个例图 ( 2 ) ( 【1 6 1 ) 投影平面的线图由它的谱刻画 ( 3 ) ( 【1 7 1 ) 当r + 1 8 时，参数为( 1 b ，r ，1 ) 的b i b d 的线图由它的谱 刻画。后来又有研究表明这一限制条件可去掉。 ( 4 ) ( ( 1 j ) 有限仿射平面的线图总能由它的邻接谱刻画 湖南师范大学硕士学位论文 4 对有向图的谱刻画，b e k p a s 和j 5 l l r n e r ( 1 8 ) 有如下结论；设 h 是有礼( 忆是一素数) 个顶点且有一循环邻接矩阵的有向图( 或图) 的全体，则与h 不同构的有向图有不同的谱 图g 的l a p l a c i a n 矩阵的特征值( 简称l a p l a c i a n 特征值) 和邻接矩 阵a ( c ) 的特征值( 简称邻接特征值) 都是图的不变量由于在l a p l a - c l a n 矩阵的定义中揉进了顶点的度，因而l a p l a c i a n 特征值更能反映 图的图论性质所以l a p l a c i a n 特征值的研究越来越受到广泛关注 在文献 8 的结尾，d a m 提出了如下一些亟待解决的问题： ( aj 哪些树由它的谱确定? 或者，哪些树与其它的树不同谱? ( b ) 对角矩阵d ，邻接矩阵a ，及所有元素都是1 的矩阵。i 的哪些线性 组合能使最多的图由它的谱确定? ( c ) 改进由邻接矩阵a ，a 的补再= l ，一a 一，l a p l a c i a i l 矩阵厶：d a ， i l l = d + a 所确定的图的数目的下界2 a 、j 2 ( ( ) 哪些最小邻接特征值为一2 的图由它的谱确定? 受这篇文章的寤发，本人开始进行这个问题的研究本文仅对 第一个问题做了小部分地研究，主要用l a p l a c i a a 谱刻画了一些结构 特殊的树以及两类特殊多图，同时用邻接谱刻画了一类特殊的似星 树 本文是如下安排的：在第二章，介绍本文需要的一些基本引理； 第三章，介绍并证明如下的主要结论： ( 1 ) 图磊( 一类特殊的似星树) 既由它的邻接谱确定，又由它的l a p l a c i a n 谱确定； ( 2 ) 2 图磊的不相交的并磊，+ 瓦。+ + 磊。髓由其邻接谱确定，其 中，礼h ，n 。都是大于1 的正整数；个不相交的圈磊的并七磊 能由其l a p l a c i a n 谱确定； ( 3 ) 似星树( 包括星图) 由它的l a p l a c i a n 谱确定； ( 4 ) 梳图由它的l a p l a c i a n 谱确定； ( 5 ) 饱和烷烃分子g 凰。+ 2 的一个同分异构体的分子图由它的l a p l a - c l a n 谱确定； 湖南师范大学硕士学位论文 5 ( 6 ) 6 眠和其它两类似双星图虽不能由它们的邻接谱确定，但能由它 们的l a p l a c i a n 谱确定； ( 7 ) 恰有一个l a p l a e i a n 特征值大于3 的树由它的l a p l a c i a n 谱确定； ( 8 ) 恰有两个l a p l a c i a n 特征值大于2 的树( 包括双星图) 都能由它们 的l a p l a c i a n 谱确定； ( 9 ) 多图l 。( 尬。) 和c 4 ( 瓦。) 由它们的l a p l a c i a n 谱确定 湖南师范大学硕士学位论文 6 第二章基本引理 在本文中，所有的图都指无环或无平行边的不定向图所有这 里未定义的概念能在【1 9 中找到设g = ( ke ) 是n 阶( 简单) 图，其 度矩阵和邻接矩阵分别记为d ( g ) = d i a g ( d 。：钍v ) 和a ( g ) = ( 。) ， 其中也是顶点u 的度；当u 和”相邻时a 。= 1 ，当“和口不相邻时 。= 0 则图g 的l a p l a c i a n 矩阵定义为c ( g ) = d ( g ) 一a ( g ) 记g 的邻接矩阵a ( g ) ( 或l a p l a c i a n 矩阵g ( g ) ) 的特征多项式为r g ) ( a ) ( 或 r 牺) ( u ) ) ，它们的特征值和谱也分别称为图g 的邻接( 或l a p l a c i a n ) 特 征值和邻接( 或l a p l a c i a n ) 谱由于a ( g ) 和c ( g ) 都是实对称矩阵，它 们的特征值都是实数因此我们可分别设入、( g ) 入。( g ) 2 。( g ) 和芦l f g ) p z ( g ) p 。( g ) ( = 0 ) 是图g 的邻接特征值和拉普拉斯 特征值 下面的引理将在本文中经常用到： 引理2 0 1 俐设a ，b 是两个n 扎矩阵，下面的命题是等价的： f 矽a 和b 同谱； 一z ，- t 和b 有相同的特征多项式； “z 砂t r ( a 2 ) = t r ( b 。) i = 1 ，2 ， 如果a 是一个图的邻接矩阵，则t r ( a t ) 给出了该图中长为i 的 闭回路的总个数因此，对任意给定的i ，同谱的图中都有相同数目 的长为i 的闭回路尤其，它们有相同的边数( 取i = 2 ) 和三角形 的数目( 取i = 3 ) 引理2 0 2 俐在一个没有4 一圈伥度为4 的圈j 的图中，长为4 的 闭回路的数目等于边数的2 倍加上长为2 的子图路仰r 的数目的 4 倍 引理2 0 3r 俐设a 是一个h e r m i t i a n 矩阵，特征值为a 一，a 。，b 是它的一个主子式；设b 有特征值“。则下面的不等式成立： a + ts “ s 九，i = 1 ，r n 引理2 0 4 ( c o u r a n t w e y l 不等式， 2 0 ) 设m 俩) 兰p 2 江) 湖南师范大学硕士学位论文 ，7 如( x ) ) 是实对称矩阵x 的特征值a 和b 是阶为n 的实对称矩阵 若c = a + b ，则 弘”j + l ( c ) 卢一i ( a ) + 卢升1 ( 口) 这里0 i ，j ，i 十j n 尤其， 弘1 ( c ) p 1 ( a ) + “1 ( b ) 引理2 0 5 似圳若y 是x 的子图，则a 。( y ) a 。( x ) 进一 步，当y 是x 的真子图时，等式成立仅当x 是不连通的 引理2 0 6 他i ) 设图g 去掉一条边后所得的图为g 则 芦。( g ) 2m ( a ) p 。+ l ( g ) ， 这里i = 1 ，2 ，n 一1 ， 我们把图g 关于l a p l a c i a n 矩阵的特征多项式写成如下形式： p c ( c ) ( u ) = f 芦，一g ( g ) f = q o # “+ q 1 弘”一1 + + q 。一1 弘+ q n ， 并总结了( 2 2 】中的一些结论如下： 引理2 0 7 设图g 有n 含顶点和m 条边令d = ( d 。，“) 是它的 不增度序列，则岛( g ) ( 肛) 中的一些系数为： 帅= 1 ：口1 = 一2 盯l ；口2 = 2 m 2 一m 一；d 2 ；q n 一1 = ( 一l r 一1 n s ( g ) ；= o ； 这里，s ( a ) 是g 中生成树的数目 关于一个图和它补图的l a p l a c i a n 谱的关系有如下结论： 引理2 0 8 懈，2 4 ) 设图x 有礼个顶点，叉是它的补图，则胁( x ) ： n 一# n - i ( x ) ，1 i 礼一1 引理2 0 9 设图g 中， v ( c ) 啦e ( g ) o 则 ( | 2 5 。2 6 , 2 1 ) ( g ) + 1 p ，( g ) s m 口z 堡堕二二专 车掣, u v c e ( g ) ) 湖南师范大学硕士学位论文 8 这里，a ( c ) 表示g 中顶点的最大度，n 。表示g 中与顶点口相邻 的所有顶点的平均度和 f z 秒r 2 劬著图g 是至少有两个顶点的连通图，则m ( g ) = ( g ) + 1 当且仅当 y ( g ) i = a ( g ) + 1 ( i i i ) r 2 s ) 若g 是至少有两个顶点的连通图，则芝d 2 ，这里d 2 是图 g 中顶点的第二大度 引理2 0 1 0 似9 ) 设树r 有礼个顶点，l ( t ) 是它的线图则“( 了1 ) = a “己( 丁) ) + 2 ，这里i = 1 ，2 ，n 一1 ，a ；( l ( t ) ) 是图l ( t ) 的第i 大邻接特 征值 用x ( g ) = x ( g ，x ) = d e t ( z i a ( g ) ) 表示邻接矩阵a ( g ) 的特征多 项式，p ( c ) 表示a ( g ) 的最大特征值 引理2 0 1 1 刚设a ，b 是图g 中相关联的顶点，d 。 1 ，d b 1 在 g 的相邻顶点a 和b 上分别接出路r 和b ，记使得的图为g f 则当 k l 1 且z p ( g 卜1 ) 时成立 从而特别有 x ( g 膏，“z ) p ( g + 1 ，f t ) 恰餮一个顶点的度大于2 的树称为似星树( 见弘1 】) 关于似星 树，我们有如下结论： 引理2 0 1 2 ( 3 圳任意两个非同构的似星树关于邻接矩阵都不同谱 引理2 0 1 3 似星树的第二大l a p l a c i a n 特征值小于5 。特别地，所有 最大度为3 的似星树的第二大l a p l a c i a n 特征值都小于4 证明r 设t 是一棵似星树考虑矩阵g ( t ) 去掉最大度的顶点所在 酌行和列后得到的主子阵m 显然，m 是一些矩阵的直和这些矩 阵或者阶为1 ，或者形为c = a + b ，这里 湖南师范大学硕士学位论文 9 a = b 是某条路的l a p l a c i a n 矩阵显然a ，b 和c 都是对称矩阵由于a 的最大特征值是1 ，b 的最大特征值小于4 ，所以，由引理2 0 4 知c 的最大特征值小于5 ，故m 的最大特征值小于5 因此，由插值定理 吲理2 0 3 ) ，p 。( t ) 5 注意到最大度为3 的每棵似星树在去掉与3 度 顶点关联的一条边后，所得的图是两条不相交的路图的并( 或一条路 加上一个孤立点甄) 而昂的l a p l a c i a n 谱为2 + 2 c o s 熹鲁，i = 1 ，- n ( 参见 8 】) 所以“，( 只) 1 ) ，或k 。假设0 中有t ( t 1 ) 个路 图分支因为每个路图分支中b 数比有相同顶点数的最大度为3 的 似星树中恳少1 ，所以g 中p 3 数比磊，+ 磊。+ + 乙。中b 数少t 由引理2 0 2 知，0 中长为4 的闭回路数少于磊。+ 磊：+ + 乙。中 长为4 的闭回路数矛盾! 所以0 中没有路图分支于是g 中每个 分支恰有一个顶点度为3 进一步，g ，( 见图3 3 ) 不是0 的分支： 因为g ，的邻接谱中含有一个特征值1 ( 见 1 】第2 7 6 页) ，而1 不是 磊，+ 磊。+ + 磊。的邻接特征值由于下面三个图( 见图3 4 ) 都有 最太邻接谱为2 ( ，第2 7 6 页) ，所以，由，引理2 0 5 ，图g 。，g 5 g 6 都不 能是0 的分支 湖南师范大学硕士学位论文 1 3 i 1 ，h l h 。0 h g 4g 5g 6 图3 4 最大邻接特征值为2 的三个图 因此0 中可能的分支是g 2 ，g 3 ( 见图3 3 ) ，z 。( m 1 ) 或蜀同 时，从它们的邻接谱中我们知道，0 中所有的分支不可能全是g 。， 或全是g 。，或1 其次，我们证明g 。，g 。，k 。也不是0 的分支假设0 是a g 。+ ，g 3 十磊，+ 十：+ c 甄，这里a + b + c + l = k ，n b ，f 都是正整数，c 是非 负整数我们断言+ 十。的每个分支正是乙。+ + 磊。的分 支用反证法来说明这一事实假设在乙。+ + z m ，和乙，+ + 磊。 间有t ( o t f ) 对同构的分支从图e 和乙，+ + 磊。中同时去掉 这t 对分支，并把剩下的图分别记为s 和s 7 ，这时，s 和s 7 同谱 于是在。+ + 磊。中有。( k a b c t ) 个分支( 不妨设为 磊。，瓦。) 与s 中的任意分支都不同构假设乙是这。个分支 中最大的一个分支，于是磊的谱是s 7 的某个( 或某些) 分支的谱 的一部分但不是全部由于2 c o s j 五巯是磊的一个特征值，那么在 s 7 和s 的谱中都应至少有一个特征值为a = 2 c o s 而葡b 雨t ( m 是某 个正整数) 由于磊是。，。+ 中最大的分支，因而a 是g 。或 g 3 的特征值 如果a 是g 。的特征值，那么等式a = 2c o s 朵成立，解得凡= 2 ， m = 2 或他= 4 ，m = 1 如果n = 2 ，那么，+ + ，+ 的每个分支都 是易于是s 7 和s 都有最大邻接特征值为2 c 0 8 葡7 1 ，重度为b ，以及另 一个特征值2 c o s 矗( 它是g 。的最大特征值) ，重度为o 从而在s ，中 恰有n 个磊分支和b 个五a 分支所以s 7 有特征值2c o s 器，但它不 是s 的特征值矛盾 如果n = 4 ，则z m 。，+ + z m 。中可能的分支是 z 2 ，或磊，或邑与上面的证明类似，我们可以得出：。+ + z 中的分支不可能全是邑( 或玩) 假设z 3 是。+ + 磊，的一个分 支，因为2 c o s 是历的特征值，则2 s 面 葡( m 7 是某个正整数) 应 是的一个特征值( 理由同上) 丽它却既不是磊的特征值，也不是 的特征值所以磊不会是。，+ + z m ，的分支因此扬和蜀 都是z m ，+ + z m 。，的分支从而s 中恰有a 个磊分支和b 个死 分支因为，+ + z m 。中的这。个分支与s 中的任一分支都不 同构，从而迫使s 7 中余下的x + c 个分支都是甄这与我们的题设矛 盾! 类似地，我们得出a 也不是g z 的特征值所以苏，+ + z m ；的每 个分支正是乙，+ + 磊。的分支从而a g 2 + b g 3 + c k l 与磊。+ + 磊。 去掉乙，+ + z 。后的图同谱但从它们的谱中我们知道这不可 能同样，图0 既不是a g 2 + 瓦，+ + 。+ c k l 的形式，也不是 b g 3 + ，+ + ，+ c k 。的形式，这里a ，b ，l 都是正整数，c 是非负 整数 最后，从磊的谱申我们很容易发现：图0 也不是z m ，+ z 。，+ + z m ；+ c k 。的形式，这里f c 都是正整数所以g 是磊，+ + 乙。 帆，m * ) 中最大的整数( 不妨设为r e + ) 从最大的特征值中可以得 到，而 m 一，m e 中次大的整数可从磊。+ 乙：+ + 磊。及其谱中去掉 乙，和它的谱后的最大特征值中得到，依此类推，可得出 m 。，帆 的所有值口 我们很容易从它们的邻接谱中发现下面的结论： 推论3 1 5 俐图马。+ 1 俭有2 n + 1 个顶点的路i i t ) + k , 与图只+ 瓦 关于邻接矩阵同谱；尤其，图只。+ 3 + 2 k a 与图易。+ l + 乙+ r 关于 邻接矩阵同谱 一妙图马r l + ( r 一2 ) 与图邑一一l + + 西+ z 3 + b 关于邻接 矩阵同谱，r 2 3 考虑最大邻接特征值小于2 的所有图：因为图g ，k 。的最大 邻接特征值都等于2 ，所以最大邻接特征值小于2 的图是最大度至多 为3 的树因为w 0 的最大邻接特征值是2 ，所以最大邻接特征值小 于2 的图恰有一个3 度顶点或没有3 度顶点，又因为g 4 ，g 。，g 。不能 作为其子图，所以最大邻接特征值小于2 的图只可能是：( 1 ) 磊或 死m 7 ) ；( 2 ) 路；( 3 ) 孤立点由上证明可知，这些图都能由它们的 邻接谱确定所以我们可得如下引理： 推论3 1 6 最大邻接特征值小于2 的图由它们的邻接谱确定 湖南师范大学硕士学位论文 1 5 - 3 2似星树由它的l a p l a c i a n 谱确定 星图不能由它的邻接谱确定，如下图( 见 1 1 ) ： 。r 1 i l _ t - 一 图3 5 与耳a 同邻接谱不同构的图 我们将证明它能由l a p l a c i a n 谱确定 定理3 2 1 星图由它的l a p l a c i a n 谱确定 证明：由引理2 0 9 知，墨图k 。( n 为任意正整数) 的最大l a p l a c i a n 特征值为n + 1 设图g 7 与星图k ，。有相同的l a p l a c i a n 谱由引理 2 01 ，2 0 7 知，图g 7 与k 1 。有相同的顶点数，边数以及生成树的数 目因为髓。只有一棵生成树，所以图g 7 是顶点数为n + 1 的树 因为弘1 ( g ) = p 1 ( k i ，。) = n + 1 ，由引理2 0 。8 知，f k ( 虿) = 0 ，所以虿不 连通由于每棵非平凡树至少有两个1 度顶点( 即悬挂点) ，所以， 不妨设”为g ，中的悬挂点，且乱与v 在g 中邻接则在万中，除 了“外，”与其余的顶点都邻接因为虿不连通，所以在虿中， 顶点“与其它的顶点都不邻接( 即顶点u 是虿中的孤立点) 因而 在g 中“与其它所有顶点都邻接，即顶点乱的度为他因为g ，是有 n + 1 个顶点的树，所以图口中除顶点“外，其余的顶点互不邻接， 否则图g 7 含有奇圈所以图g 是，( 1 。 口 下露我们将证明所有的似星树由它的l a p l a c i a n 谱确定由于