论文部分内容阅读
图谱理论是图论研究的一个非常活跃而又重要的研究领域,它在量子化学、统计力学、计算机科学、通信网络以及信息科学中均有着广泛的应用.图谱的研究主要是利用线性代数、矩阵论等成熟的理论和技巧,巧妙地把图的一些基本结构性质和它的参数联系在一起,并找出它们之间的内在关系.在图谱理论中,为了研究图的性质,人们引入了各种各样的矩阵.常见的有图G的邻接矩阵A(G)、拉普拉斯矩阵L(G)、关联矩阵M(G)、距离矩阵D(G)以及无符号拉普拉斯矩阵Q(G)等等.这些矩阵都与图的结构都有着密切的联系.图谱理论的一个主要问题就是研究图的性质能否以及如何由这些矩阵的代数性质(主要是指矩阵的特征值性质)反映出来.(一)在第一章中,我们首先回顾了图论的整个发展过程,接着介绍了一些常见的谱理论研究中相关的问题的代数图论背景和研究技巧.在第二小节中,我们给出了一般的图论中的一些基本概念和记号.文章中一些特殊的定义未在此节中出现的,我们将在后面的相关章节中具体介绍.在第三小节中,我们简单介绍了和本文相关问题的一些进展及最新结果.(二)在第二章中的第一、二小节中,我们研究了在顶点数为n,色数为χ和弧连通度为后的有向图中谱半径的上界,并且刻画了达到上界的极图.在本章的最后一节中,我们讨论了在强连通的双圈有向图中,谱半径到达最大和最小的极图,并且证明了所有的双圈有向图都是谱唯一的.(三)在第三章中,我们首先在第一节我们给出了q1(G)-μ1(G), q1(G)-λ1(G)和μ1(G)-λ1(G)的可达上下界,并且刻画了达到上下界时的极图.另外我门给出了q1(G)+q2(G)的可达下界.在第二节中,我们首先给出了一个图去掉一些点之后谱半径和最小根的上下界,证明了文献[2,3]中的关于谱半径、直径的一个猜想.最后我们刻画了在拟树图中,最小根达到最小的极图.在本章的最后一节,我们刻画了(二部图)图的邻接矩阵中第二大特征值达到最大的可达界.(四)在第四章中,我们首先在第一小节中考虑在有向图和无向图中,在点、弧(点、边)连通度给定的所有有向图(无向图)中,距离谱半径达到最小的极图.在第二节中,我们刻画了在所有的连通图中距离矩阵的最小根λn(D)=-2的所有图.而且,我们刻画了在直径为2的条件下,距离矩阵的最大根不是整数恰好只有3个不同特征值的连通图.在最后,我们猜想完全k-部图是D-谱唯一的.