只有三个不同特征值的图

来源 :中国科学技术大学 | 被引量 : 0次 | 上传用户:chamcham
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设图G是一个简单连通无向图,其邻接矩阵A的特征值称为G的特征值.图G的谱是指由G的所有特征值和它们对应的重数组成的集合.  本文主要围绕图谱理论中的两个问题展开研究工作.第一个问题是除去完全二部图和强正则图,寻找只有三个不同的特征值的连通图.第二个问题是研究刻画第二大特征值不超过1的图.  第一章介绍图论与图谱理论中的基本概念以及问题的研究背景.  第二章仅考虑非正则连通图.首先刻画了只有三个不同的特征值且其补图不连通的图,给出了只有三个不同特征值的图的阶,顶点度,特征值以及Perron-Frobenius特征向量的估计.证明了如果一个图和它的补图都恰好有三个不同的特征值,则此图只有两个不同的顶点度.  其次重点研究了只有三个不同的特征值且恰有两个不同的顶点度的连通图,即所谓的强双正则图.主要的结果包括强双正则图的一些结构定理,构造出了一些新的强双正则图,刻画了已知的一类特殊的强双正则图以及给出了两类有无穷多个可行的强双正则图.  最后,在已知的仅有有限个恰好有三个不同特征值和三个不同顶点度的图的基础上,又构造出了一个新的图.而且证明了一些具有特定的谱和顶点度的图是不存在的.  第三章证明了一个关于强双正则图的拟Neumaier定理,即证明了对于给定的正整数m,只有有限多个最小特征值不小于-m或者第二大特征值不超过m的非二部的强双正则图.  第四章确定出了只有三个不同特征值且第二大特征值不超过1的连通图,并且也确定出了只有三个不同的特征值且最小顶点度不大于6或者最大特征值不超过7的连通图.
其他文献
自从R.A.Fisher提出了现代统计学的理论后,试验设计在统计学的实践和应用中发挥了重要的作用,它被广泛的应用于许多科学研究领域,如农业、生物、化学等。试验设计的一个主要任务
关于两台恒同机器的排序问题,在分批排序和经典排序中,大多数文献都是考虑或者两台机器都是批处理机(批容量无界)或者两台机器都是正常机器(任何时刻最多只能加工一个工件,即