论文部分内容阅读
图谱理论是图论研究的一个非常活跃而又重要的研究领域,它在量子化学、统计力学、计算机科学、通信网络以及信息科学中均有着广泛的应用。图谱理论的研究主要是利用成熟的代数理论和技巧,并结合图论和组合数学的理论来研究图谱、图的结构性质以及与图的其它不变量(如色数、度序列、直径、围长、连通度等)之间的关系,它将图与网络的代数性质与其拓扑性质紧密地结合在一起。在图谱理论中,为了研究图的性质,人们引入了各种各样的矩阵,诸如图的邻接矩阵、关联矩阵、距离矩阵、拉普拉斯矩阵等等,这些矩阵与图的结构都有着密切的联系。图谱理论的一个主要问题就是研究图的性质能否以及如何由这些矩阵的代数性质反映出来,这里所说的矩阵的代数性质,主要是指矩阵的特征值所刻画的性质。在上面所提到的矩阵中,最重要的两个就是图的邻接矩阵和图的拉普拉斯矩阵。图的邻接矩阵的特征值和图的拉普拉斯矩阵的特征值都是在图的同构下的不变量.对图的邻接矩阵特征值而言,最重要的两个特征值是最大特征值和最小特征值,分别称为图的谱半径和最小根.对图的谱半径的研究,文献中存在大量的结果,已经形成了比较完善的理论体系。而对最小根而言,研究的结果还很少。在图的拉普拉斯特征值中,最重要的也有两个:图的最大拉普拉斯特征值(即拉普拉斯谱半径)和图的次小拉普拉斯特征值(即代数连通度)。本文主要围绕图的最小根和拉普拉斯谱半径进行研究,首先介绍图的最小根和拉普拉斯谱半径的研究背景和进展,然后分四部分详细地介绍我们围绕这两个课题所取得的主要研究成果。主要结果如下:
⑴在第二章中我们讨论直径固定的一般图。用(?)n,d表示直径为d的n阶连通图的集合。对任意的图G∈(?)n,d,通过考虑图G的连通生成二部子图的最小根,我们获得了图G的最小根的一个下界。进一步地,作为一个推论,给出了图G的拉普拉斯谱半径的一个上界。
⑵在第三章中我们研究图的最小根与图的不变量.用u(n,κ)表示悬挂点数为κ的n阶单圈图的集合.利用移接变形的技巧和特征多项式的一些技巧,刻画了最小根达到最小的单圈图。用B(n,k)表示悬挂点数为κ的n阶双圈图的集合。综合利用图谱理论的多种工具和手段,确定了最小根达到最小的双圈图.在本章的最后一节,我们考虑了图的不变量直径.用U(n,d)表示直径为d的n阶单圈图的集合,结合图的不变量直径,我们刻画了最小根达到最小的单圈图。
⑶在第四章中我们讨论三圈图的谱。用Tn表示n阶三圈图的集合.对n〉52,我们确定了最小根取到最小的唯一的三圈图。
⑷在第五章中我们讨论树的拉普拉斯谱半径.用Tn,d表示直径为d的n阶树的集合。对d∈{1,2,3,4,n-4,n-3,n-2,n-1},我们分别确定了此时拉普拉斯谱半径达到最小的树。