乔晓云

(山西大学商务学院理学系，太原030031)

设G=(V，E)是n阶简单图，其顶点集为V(G)={ν1，ν2，…，νn}，dG(νi)为顶点 νi在图G中的度数，简记为dνi，并假定对顶点进行适当排序使得度序列满足dν1≥dν2≥…≥dνn.对任意的u∈V，它的相邻点度的平均值称为u的平均二次度，记为mu，即mu=记D(G)=diag(dν1，dν2，…，dνn)和A(G)分别是图G的度对角矩阵和邻接矩阵，则图G的拉普拉斯矩阵定义为L(G)=D(G)-A(G).易证L(G)是一个半正定的、实对称矩阵，且它的每一行的行和为0，从而可以假设它的特征值为:λ1(G)≥λ2(G)≥…λn(G)=0，其中λ1(G)称为图G的最大拉普拉斯特征值。研究拉普拉斯矩阵的特征值有着重要的理论和实际意义，它在计算机网络、物理、化学和生物中有着广泛而重要的应用[1-2]，因而一直受到关注。近年来关于拉普拉斯特征值的研究，特别是最大拉普拉斯特征值的上界的估计有了不少代表性的结果。

2001 年，J.S.Li和 Y.L.Pan[3]给出了:

其中等式成立当且仅当G为正则偶图。

2004 年，X.D.Zhang[4]给出了

其中等式成立当且仅当G为正则偶图或半正则偶图。

本文的目标是利用图的顶点度，平均二次度结合非负矩阵谱理论给出图的最大拉普拉斯特征值的上界估计式，并和这些已知上界估计式进行比较，说明在某些情况下优于已知结果。本文未定义而直接引用的术语和符号参见文献[5].

1 引理和主要结果

设K(G)=D(G)+A(G)，称为G的拟拉普拉斯矩阵.熟知当G是连通图时，K(G)是非负，实对称和不可约矩阵。记ρ(K)是K(G)的谱半径。

引理1[6]设M为非负不可约矩阵，ρ(M)为M的谱半径，则存在一个正特征向量X使得MX=ρ(M)X.

引理 2[7]设G=(V，E)是n阶连通图，则λ1(G)≤ρ(K)，其中等式成立当且仅当G是偶图。

引理3[8]设G=(V，E)为r正则图，则 ρ(K)=2r.