图的最大和次小拉普拉斯特征值

摘要

设G是n阶简单连通图，D和A分别为图G的度对角矩阵和邻接矩阵，L(G)=D-A称为图G的拉普拉斯(laplacian)矩阵。研究图的拉普拉斯矩阵的特征值有着重要的图论意义和实际意义，因为它与图的许多不变量有着密切的联系。在许多应用中，往往需要知道图的拉普拉斯矩阵的最大特征值μ1(G)的上界和次小特征值μn-1(G)的上下界。本文针对μ1(G)的上界和μn-1(G)的上下界的估计问题做了以下几个方面的工作： 1.综述了近年来有关μ1(G)的上界估计的主要结果，并作了全面的比较分析。 2.利用非负矩阵行和与它的谱半径之间的关系以及Perron-Frobenius定理等方法并结合图论性质获得了图的拉普拉斯谱半径的一些上界，并附带得到了关于有向图的谱半径估计的一些上下界。同时，对其中的一些估计式，用例子说明了其准确性和易于(编程)实现性。 3.利用矩阵理论和树的一些性质，研究了Bethe树的拉普拉斯谱半径的估计问题，得到了其具体特征多项式和它的谱集。 4.图的拉普拉斯次小特征值与图的代数连通度有关系，利用矩阵分拆技巧通过将L(G)分拆为两个矩阵和的形式再利用著名的Weyl定理，给出了一类具有割点、割边图的拉普拉斯次小特征值的上下界估计式。这些估计式具有递推特征，即估计式将高阶图类的拉普拉斯次小特征值用低阶图的拉普拉斯次小特征值来表示。

目录

文摘

英文文摘

声明

第一章绪论

1.1预备知识

1.2研究背景

1.3研究图的拉普拉斯特征值的基本方法

第二章图的拉普拉斯谱半径

2.1简单图的拉普拉斯谱半径上界估计的情况

2.2图的拉普拉斯谱半径的新的估计式

2.3图的拉普拉斯谱半径的上界估计式的比较

2.4有向图的谱半径

第三章树的拉普拉斯谱半径

3.1 Bethe树与广义Bethe树的基本概念

3.2带有权值的广义Bethe树的拉普拉斯特征值

3.3图Brk,w的拉普拉斯矩阵的谱半径

第四章图的运算和图的次小拉普拉斯特征值的关系

4.1添加割边或割点的图的次小拉普拉斯特征值

第五章结论和若干尚待研究的问题

致谢

参考文献

攻硕期间取得的研究成果