若干图类的谱特征问题研究
设G是一个简单图,M=M(G)是按照某种规定所定义的与G相联系的图矩阵,
把利用M的特征值来刻画图G的组合结构的理论称为图谱理论(M-谱理论).定义det(xI-M)为图G的M-特征多项式,其中I为单位矩阵.M-特征多项式的特征根称为图G的M-特征值,由G的所有M-特征值构成的多重集称为M-谱,简记为
SpecM(G).图G的最大M-特征值称为M-谱半径.关于图矩阵M具有相同谱的图称为M-同谱图,与G图M-同谱但不同构的所有图称为图G的M-同谱类.如果G不存在M-同谱但非同构的图时,则称G是由M-谱确定的.即对任意的图
H,SpecM(H)=SpecM(G)蕴含着H～=G,简记为DMS-图.特别地,当M等于邻接矩阵A、拉普拉斯矩阵L=D-A和无符号拉普拉斯矩阵Q=D+A时,便是图G的A-谱、L-谱以及Q-谱的相关概念,这里D为G的度对角矩阵.图的谱特征问题主要考虑图矩阵
的谱性质和谱刻画问题.从目前的研究状况来看,图矩阵主要包括关联矩阵、邻接矩阵、拉普拉斯矩阵、无符号拉普拉斯矩阵、距离矩阵、标准拉普拉斯矩阵、Seidel 矩阵、广义邻接矩阵等.对于谱性质而言,谱半径及其相关参数的研究一直是图谱问题研究的重要组成部分.同时,第二大、第三大特征值以及某些图矩阵的最小、次小特征值也是比较热门的研究课题.谱刻画问题主要是通过某些谱特性来刻画具有这种谱特性的图,其中谱确定问题是谱刻画中十分棘手的问题之一,也是整
个图谱问题研究的核心问题.从已知的DMS-图来看,谱确定的研究主要集中在三
类图上.第一类是结构相对简单,对称性较好的图;第二类是至多含有四种不同度数的非正则图;第三类是能被度序列唯一确定其形状的图.然而,对于上述三类图而言,要判断任意给定的图是否是DMS-图也是一个相当困难的问题.本文主要借
助于图结构、组合理论、矩阵理论、闭道数公式、特征多项式、特征向量、特征
值及其界、谱矩量和度序列重点研究了一些图类的谱确定性问题,同时也考虑了其他一些图类的谱性质.在图谱确定方面,我们主要围绕“一个图是否是谱确定的?如若不是,能否确定出其同谱类?”这两个问题展开.文中第二章、第三章、第四章分别主要研究了一些图类的邻接谱、拉普拉斯谱以及无符号拉普拉斯谱的谱确定问题,第五章通过图运算构造了若干图的无穷同谱类.本文的具体组织结构如下:第一章主要介绍了图谱理论的研究背景,接着引入了本文所用到的符号与概念.随后对谱特征问题的起源以及研究现状作了概述.最后简要地介绍了本文的主要结论.第二章首先通过考虑主向量得到了杠铃图(barbell graph)A-谱半径的一个比较紧的上界与下界;紧接着,我们给出了杠铃图的A-特征多项式谱半径方程.其次,考虑了T-形树(T-shape tree)线图的A-谱刻画,我们证明了T-形树线图除一些图类外是由A-谱确定的.同时,给出了这些图类的同谱图.第三章首
先考虑了图的L-谱与子图填充数(packing number)之间的关系.其次,我们研究了T-形树的线图、Π-形树(Π-shape tree)与风轮图(windwheel graph)的L-谱刻画.在T-形树线图的L-谱刻画中,证明了两个T-形树的线图同谱一定是同构的;在Π-形树的L-谱刻画中,我们证明了其中一类Π-形树除一个无穷同谱类外是L-谱确定的.有趣的是,在这类Π-形树中我们找到了树图的一个无穷L-同谱类.在风轮图的L-谱刻画中,证明了所有风轮图是L-谱确定的.最后,我们主要研究了一些L-谱确定的可图度序列及其对应的图.第四章首先研究了Q-谱的一些基本性质,这些性质可以看做是A-谱性质在Q-谱方面的平移.其次证明了风轮图是Q-谱确定的,并由此结论推知友谊图(friendship graph)也是由Q-谱确定的.第五章根据图G1,G2和G3,分别确定了剖分点-边邻接点-冠图(subdivision vertex-edge neighbourhood vertex-corona)GS1??(GV2∪GE3)与剖分点-边邻接
边-冠图(subdivision vertex-edge neighbourhood edge-corona)GS1(GV2∪GE3)的A-谱,L-谱以及Q-谱.作为对它们的应用,我们构造了若干无穷同谱类.与此同时,我们还给出了图GS1??(GV2∪ GE3)与GS1(GV2∪ GE3)的生成树的数目.。