论文部分内容阅读
设图G是一个简单连通无向图,其邻接矩阵A的特征值称为G的特征值.图G的谱是指由G的所有特征值和它们对应的重数组成的集合. 本文主要围绕图谱理论中的两个问题展开研究工作.第一个问题是除去完全二部图和强正则图,寻找只有三个不同的特征值的连通图.第二个问题是研究刻画第二大特征值不超过1的图. 第一章介绍图论与图谱理论中的基本概念以及问题的研究背景. 第二章仅考虑非正则连通图.首先刻画了只有三个不同的特征值且其补图不连通的图,给出了只有三个不同特征值的图的阶,顶点度,特征值以及Perron-Frobenius特征向量的估计.证明了如果一个图和它的补图都恰好有三个不同的特征值,则此图只有两个不同的顶点度. 其次重点研究了只有三个不同的特征值且恰有两个不同的顶点度的连通图,即所谓的强双正则图.主要的结果包括强双正则图的一些结构定理,构造出了一些新的强双正则图,刻画了已知的一类特殊的强双正则图以及给出了两类有无穷多个可行的强双正则图. 最后,在已知的仅有有限个恰好有三个不同特征值和三个不同顶点度的图的基础上,又构造出了一个新的图.而且证明了一些具有特定的谱和顶点度的图是不存在的. 第三章证明了一个关于强双正则图的拟Neumaier定理,即证明了对于给定的正整数m,只有有限多个最小特征值不小于-m或者第二大特征值不超过m的非二部的强双正则图. 第四章确定出了只有三个不同特征值且第二大特征值不超过1的连通图,并且也确定出了只有三个不同的特征值且最小顶点度不大于6或者最大特征值不超过7的连通图.