论文部分内容阅读
在图论中,为了研究图的性质,人们引进了各种各样的矩阵,诸如图的邻接矩阵,关联矩阵,距离矩阵.拉普拉斯矩阵等。这些矩阵与图都有着自然的联系,代数图论的一个主要问题就是研究图的性质能否以及如何由这些矩阵的代数性质反映出来。这里所指的矩阵的代数性质,主要指矩阵的特征值。
在上面所提到的矩阵中,最重要的有两个:图的拉普拉斯矩阵和邻接矩阵。图的拉普拉斯矩阵的特征值和邻接矩阵的特征值都是图的在同构下的不变量。在过去的几十年中,人们对图的邻接矩阵的特征值已经进行了大量的研究,目前已形成比较成熟的理论,详见专著[3,14,21]。与图的邻接矩阵的特征值相比,由于拉普拉斯矩阵的特征值与图的结构之间有着更自然的联系,更能反映图的图论性质,因此对拉普拉斯矩阵的特征值的研究正越来越引起人们的关注,是当前图论研究中的一个热点问题。
在图的拉普拉斯特征值中,最重要的一个即是图的最大拉普拉斯特征值,称为图的Laplace谱半径。近年来,对图的Laplace谱半径问题的研究,国内外都取得了一定的进展。有些学者给出了 Laplace 谱半径的一些很好的上界(见文献 [23,24,73,75,76,79,90,93,105])。另外,也有学者考虑了对某些特殊图类进行嫁接、剖分和收缩等运算后,图的 Laplace 谱半径的变化情况(见文献[47])。
本文主要是对连通图的最小Laplace谱半径的排序问题的研究。
在第一章中,我们介绍了图的Laplace谱半径的研究背景以及近年来国内外学者的一些研究成果,也介绍了代数图论中的一些基本概念。
众所周知,树是最简单的连通图。因此,我们本文的研究就从树开始。在第二章中,我们着重研究了n阶树的最小Laplace谱半径的排序。在[1]中,袁西英等运用树的嫁接、剖分和收缩运算,排出了具有最小 Laplace谱半径的前七棵n阶树。在这一章中,我们继续这个顺序,将具有最小Laplace谱半径的n阶树排至前十一棵。
我们在一棵树中任意添加一条新边即得到一个单圈图,在一个单圈图中任意添加一条新边即得到一个双圈图。因此,在随后的第三章中,我们主要研究了n阶单圈图和双圈图的Laplace谱半径,找出了具有最小 Laplace 谱半径的第2个至第5个n阶单圈图和具有最小Laplace谱半径的n阶双圈图。
结合第二章和第三章中的研究结果,在最后的第四章中,我们给出了所有n 阶连通图中Laplace谱半径最小的14个图,当n为偶数时它们达到了所有n阶连通图中 Laplauce 谱半径最小的9个值(其中有并列的),而当n为奇数时它们则达到了Laplace谱半径最小的8个值(其中有并列的)。