关于图的特征值的几个问题的研究

摘要

图谱理论是图论研究的一个非常活跃而又重要的研究领域，它在量子化学、统计力学、计算机科学、通信网络以及信息科学中均有着广泛的应用.图谱的研究主要是利用线性代数、矩阵论等成熟的理论和技巧，巧妙地把图的一些基本结构性质和它的参数联系在一起，并找出它们之间的内在关系.
　　 在图谱理论中，为了研究图的性质，人们引入了各种各样的矩阵.常见的有图G的邻接矩阵A(G)、拉普拉斯矩阵L(G)、关联矩阵M(G)、距离矩阵D*(G)以及无符号拉普拉斯矩阵Q(G)等等.这些矩阵都与图的结构都有着密切的联系.图谱理论的一个主要问题就是研究图的性质能否以及如何由这些矩阵的代数性质(主要是指矩阵的特征值性质)反映出来.尽管这些定义不同的矩阵有着各种丰富的形式，但是他们的特征多项式(或者说谱)之间却很可能是互相关联的.在[20]中，Dragos列举说明了在二部图中，无符号拉普拉斯谱和拉普拉斯谱相同.同时我们知道，图的拉普拉斯矩阵的非零特征值和它的线图的邻接特征值也有着密切的关系.这样，通过二部图就可以把它们紧密地联系在一起.又例如，令
　　 FG(x，λ)=det(xI+λD-A(G))那么，邻接矩阵的特征多项式可以表示为FG(x，0)，拉普拉斯矩阵的特征多项式可以表示为(-1)nFG(-x，1)，无符号拉普拉斯矩阵的特征多项式可以表示为FG(x，-1)等等.尽管如此，由于它们都有自己独特的应用背景和实际价值，我们还是很有必要对这些不同的矩阵和谱展开针对性的研究的.
　　 在上面所提及的矩阵中，最重要的两个就是图的邻接矩阵和拉普拉斯矩阵.本文研究的主要问题在三个方面：(1)简单连通无向图的拉普拉斯谱及其极限点：(2)有向图的邻接谱半径；(3)无符号拉普拉斯特征值的极限点和谱半径.我们试图建立它们与图的结构参数之间的一些关系.具体内容如下：
　　 (一)在第一章中，我们首先回顾了图论的整个发展过程，接着介绍了一些常见的谱理论研究中相关的问题的代数图论背景和研究技巧.在第二小节中，我们给出了一般的图论中的一些基本概念和记号.文章中一些特殊的定义未在此节中出现的，我们将在后面的相关章节中具体介绍.在第三小节中，我们简单介绍了和本文相关极限点以及谱半径等问题的一些进展及最新结果.
　　 (二)在第二章中的第一小节中，我们首先通过找到一个图序列{Gn}，证明它的第三大拉普拉斯特征值极限点存在，并且满足()而后，我们证明1和上式中1.5550分别是第三大拉普拉斯特征值的第一小和第二小极限点.在第二小节中，对固定的b，假设l3(b)和l'3(b)分别是方程bμ(μ-2)-(μ-1)2(μ-3)=0和bμ(μ-2)-(μ-1)2(μ-3)-(μ-1)(μ-2)=0的第二大根.我们证明了l3(b)和l'3(b)(b=0，1，…)都是第三大拉普拉斯特征值极限点.接着，我们确定了l3(b)和l'3(b)以及2是第三大拉普拉斯特征值在区间(0，2]内的所有极限点，并且证明了l'3(6)　　 (三)在第三章中，我们首先在第一节里刻画了所有满足其第二大拉普拉斯特征值μ2(G)≤l的连通图G，其中l()3.2470是三次方程μ3-5μ2+6μ-1=0的第一大根.在此基础上，我们通过对图的拉普拉斯特征多项式和特征值的讨论，在第二小节里求出所有小于等于l()3.2470的第二大拉普拉斯特征值的极限点.
　　 (四)在第四章中，我们首先在第一小节中考虑在有向图的一些移接变形后谱半径的变化情况，然后给出团数和围长等固定的有向图中谱半径取到最小时的极图以及强连通图的最小和第二小谱半径.最后，我们求出了点连通度给定的强连通有向图的最大谱半径.
　　 (五)在第五章中，我们首先主要以顶点度di和图的边数m为参数，通过矩阵相似变换，讨论了弱并接(weak join)图的谱半径的上界，并刻画了达到这个上界的极图.谱半径的上界的准确估计，对于考虑图的最大特征值的极限点的存在性有至关重要的作用.接着，我们根据第二章和第三章的内容，给出了无符号拉普拉斯特征值的一些极限点的存在情况.