图的最大拉普拉斯特征值

【作者】 汪天飞；

【导师】 张先迪；

【作者基本信息】 电子科技大学 ， 计算数学， 2006， 硕士

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

【Abstract】 Let G be a simple and connected graph with n vertices and H be the line graph of G. Denote D and A be the diagonal matrix of vertex degrees and the adjacency matrix of G, while DH and B be the diagonal matrix of vertex degrees and the adjacency matrix of H, respectively. Let U=diag（dudv:uv∈E（G）） be a diagonal matrix. Then the matrix L=D-A and K=D+A is called the Laplacian matrix and the Qusi-Laplacian matrix of G, separately. The Laplacian eigenvalues of a graph are important in the graph theory, because they have a close relation to numerous graph invariants. In many applications, good upper bounds forλ1（G）, the largest Laplacian eigenvalue of a graph G, are needed. In this paper, the following results are obtained:1.The main upper bounds forλ1（G） are summarized and compared in detail.2.Several new and sharp upper bounds forλ1（G） in terms of the vertex degree and the average 2-degree are obtained by applying nonnegative matrix theory to the similar matrix D^-1/2KD^1/2,D_H^-1/2BD_H^1/2 and U^-1/2BU^1/2, respectively. Moreover we determine all extremal graphs which achieve these upper bounds.And then some examples to illustrate that our results are better than the earlier and recent ones in some sense.3.An other type of upper bound forλ1（G） in terms of the degree sequence and the edge number of G are obtained by utilizing the inequality techniques and the relation of the matrix B with its eigenvalues, and we also determine the extremal graphs.4.In chapter three, some upper bounds for the Laplacian spectral radius of a graph with cut vertices or cut edges are given by separating the Laplacian matrix into two matrices and using famous Weyl theorem. These upper bounds are presented by the Laplacian spectral radius of the subgraphs of G which with large n. Furthermore, some examples show that these upper bounds are good in some cases.更多还原