论文部分内容阅读
图谱理论起源于理论化学家和物理学家为解决一类偏微分方程的数值解而建立起来的一套离散的图模型.它在物理学、化学、计算机科学及通信网络等方面都有着十分广泛的应用.图谱理论主要是利用矩阵理论中的方法和技巧,来研究图矩阵(如邻接矩阵A,拉普拉斯矩阵L=D-A,无符号拉普拉斯矩阵Q=D+A,规范拉普拉斯矩阵?L=D-12 LD-12,Seidel矩阵S=J-2A-I等)的谱(特征值及其重数)的性质进而用这些性质来反映图的一些结构性质和拓扑性质,它是代数图论中一个重要的研究领域.图谱理论研究的内容相当广泛,概括起来主要包括两个方面,一个方面是图的谱特征,主要涉及确定图的谱及其分布,确定谱的性质,谱与图的各种参数(例如直径,色数,围长,连通度等)之间的关系等;另一个方面是谱的图特征,主要是根据谱的性质刻画图等,其中图的谱确定问题是其研究的重点.两个图同谱是指它们有相同的谱.两个图同谱不一定同构,但是两个图同构则一定同谱.一个图G被称作是由谱确定的,如果对于任意一个图H,由H与G同谱蕴含着H与G同构.图的谱确定问题是指,对于一个图,首先考虑该图是否由谱确定;其次如果该图不能由谱确定则考虑找出它所有的同谱图.图的谱确定问题最早由G¨unthard和Primas提出,接着van Dam和Haemers发表了两篇综述文章对此问题进行了概括总结,并给出了很多谱确定图及图同谱的必要条件.但是“哪些图是由它的谱所确定的”这个问题还远远没有解决.从已经取得的研究结果来看,谱确定问题主要考虑具有一定特性的图,如对称性较好的图、谱半径在一定范围之内的图、特征值个数较少的图、非正则且度序列中不同度数较少的图(例如几乎正则图)等.虽然目前已经知道了很多谱确定图,但是要考虑一般图是否由谱所确定还是有很大难度的.在本文中,我们主要考虑两类图的谱确定问题,一类是第二大特征值小于等于1的单圈图的邻接谱确定问题,另一类是4-玫瑰图的拉普拉斯谱确定及无符号拉普拉斯谱确定问题.本文结构安排如下:第一章首先简要介绍了图谱理论的研究背景及应用.其次给出了本文要用到的基本概念和符号.随后对谱确定问题的来源,国内外研究现状及发展动态做了概括总结.此外,我们还引入了一些研究谱确定问题常用的工具、方法及结论.最后介绍了本文的主要研究工作.对第二大特征值不超过1的图的刻画已经取得了很多研究成果,本论文的第二章则从图的谱确定角度来研究这些图.我们主要考虑第二大特征值小于等于1的单圈图的邻接谱确定问题.首先我们对第二大特征值小于等于1的所有单圈图进行分类并且证明了具有这一性质的所有单圈图之间不是邻接同谱的.其次我们给出了与具有这一性质的图邻接同谱的必要条件并且找到了一些禁止子图.再次,我们根据分类逐一考虑了这些图的谱确定性.其中重点证明了图Gt,s是由它的邻接谱所确定的.最后,利用禁止子图条件证明了在第二大特征值小于等于1的单圈图中,除了四个图外,其它的图都是由它们的邻接谱所确定的.此外,我们还给出了不能由邻接谱所确定的那些图的同谱对.具有p个花瓣的图(简称为p-玫瑰图)是指p个圈恰有一个公共顶点的图,“玫瑰图”的得名由玫瑰曲线而来.玫瑰图的谱确定问题一直受到人们的关注.第三章我们考虑了4-玫瑰图的拉普拉斯谱确定性.首先我们介绍了两个图L-同谱的一个必要条件.其次根据4-玫瑰图的组合结构给出了它的拉普拉斯特征多项式中倒数第三项的系数.另外,我们还给出了4-玫瑰图的拉普拉斯特征多项式的表达式.最后根据4-玫瑰图的拉普拉斯谱半径的界得出L-同谱于4-玫瑰图的图可能的度序列.最终证明了4-玫瑰图是由它的拉普拉斯谱所确定的.第四章我们讨论了4-玫瑰图的无符号拉普拉斯谱确定性.我们首先引进了一个新的Q-同谱不变量并给出了4-玫瑰图的无符号拉普拉斯特征多项式的表达式.其次介绍了Q-同谱于4-玫瑰图的图可能的形.再次,利用无符号拉普拉斯谱半径的界讨论了Q-同谱于4-玫瑰图的图可能的度序列.最后利用Q-同谱图的新的不变量和图中三角形的数目证明了4-玫瑰图是由它的无符号拉普拉斯谱所确定的.