论文部分内容阅读
设图G=(V,E)是具有n顶点和m条边的简单连通图,图G的邻接矩阵A=A(G)=(αuv)n×n,其中αuv表示顶点u和v邻接,图G的邻接矩阵A(G)的特征值μ1≥μ2…≥μn,其中μ1为邻接矩阵A(G)的最大特征值,称为图G的邻接矩阵的谱半径,简记为ρ(G).D=D(G)=diag{d1,d2,…,dn}为图G的度对角矩阵,则图G的Laplacian矩阵定义为L(G)=D(G)—A(G).已知L(G)是实对称半正定的奇异M矩阵,故特征值均是非负的.又L(G)的行和均为0,故0是最小特征值,因此可假定L(G)的特征值为λ1(G)≥λ2(G)≥…≥λn-1(G)≥λn(G)=0,其中λ1(G)为图G的Laplacian矩阵特征值的最大值,称为图G的Laplacian谱半径,简记为λL(G).设K(G)=D(G)+A(G),称为图G的拟—Laplacian矩阵,其中它为非负不可约的实对称矩阵,它的特征值非负.连通图G的谱半径和图G的Laplacian矩阵的谱半径具有重要的图论和实际意义,因为它们与图论的不变量有着紧密联系,在实际生产中,对于连通图的谱半径和图的Laplacian的谱半径的估计很重要.故本文对于ρ(G)和λL(G)的估计做以下的工作.
(1)利用代数的方法和非负矩阵理论得出连通图的ρ(G)上界和达到上界的图,并且用图例说明这一些新结果对于以前的一些结果有很好的改进.
(2)在度序列和边数的条件下,利用重要不等式的方法得到与相似矩阵B有相同的特征值,λL(G)上界估计和达到上界的图.
(3)利用相似矩阵具有相同的特征值,得出简单连通图的二部图的λL(G)新上界的估计.