论文部分内容阅读
设G是n阶简单连通图，H是图G的线图，D和A分别为G的顶点度对角矩阵和邻接矩阵，DH和B分别为H的度对角矩阵和邻接矩阵，U=diag(dudv:uv∈E(G))是一对角矩阵。则L=D-A称为G的拉普拉斯(Laplace)矩阵，而K=D+A称为拟拉普拉斯矩阵。研究图的Laplace矩阵的特征值有着重要的图论意义和实际意义，因为它与图的许多不变量有着密切联系。在许多应用中，往往需要Laplace矩阵最大特征值λ1(G)的好的上界估计值。本文针对λ1(G)的上界估计问题做了以下工作：
1.综述了近年来有关λ1(G)的上界估计的主要结果，并作了全面比较分析。
2.将非负矩阵理论应用到相似变换矩阵D-1/2KD1/2，DH-1/2BDH1/2和U-1/2BU1/2并结合图论性质获得了λ1(G)的几个用顶点度数和顶点平均二次度表示的新的紧的上界。并确定了等式成立的全部极图。同时几个例子用于说明这些新的结果是不可比较的，并在一定意义上改进了现有的大多数结果。
3.将特征值与特征向量的关系应用到线图的邻接矩阵B并利用不等式方缩技巧和图的性质获得了λ1(G)的一个用图的度序列，边数表示的紧的上界估计式，并确定了相应的极图，同时举例说明在一定情况下该估计值在同类结果中最优。
4.利用矩阵分拆技巧将L分拆为两个矩阵和的形式并利用著名的Weyl定理给出了一类具有割点、割边图的Laplace谱半径的几个上界估计式。这些估计式将高阶图类的Laplace谱半径用较低阶的子图的Laplace谱半径来表示。图例表明这类结果在某些图的Laplace谱半径的估计上获到了比较好的效果。