喬曉云

(山西大學商務學院理學系，太原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為正則偶圖或半正則偶圖。

本文的目標是利用圖的頂點度，平均二次度結合非負矩陣譜理論給出圖的最大拉普拉斯特征值的上界估計式，并和這些已知上界估計式進行比較，說明在某些情況下優(yōu)于已知結果。本文未定義而直接引用的術語和符號參見文獻[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.

定理1 設G是簡單連通圖，則有:

其中等式成立當且僅當G為正則偶圖。

證明 由D的定義可知:V(G)).令，則矩陣M的第(u，ν)個元素為:

由G是簡單連通圖易知M是非負不可約的。由引理1 可知:可設向量X=(x1，x2，…，xn)T為M的對應于特征值ρ(M)的正特征向量，即MX=

由Cauchy-Schwarz不等式可知:

故存在u∈V(G)，使得:(ρ(M)-du)2-所以由引理2可知:

當式(3)中等式成立時，以上證明過程中的不等式均為等式，則存在u∈V(G)，使得 ρ(M)=根據式(4)可知，故存在w∈V(G)但w≠u，使得，即:

由引理2知G為偶圖。假設(S，T)是V的一個分割，不妨設u為T中的最大度點，u'為T中的最小度點，則有，且，結合取遍V(G)中的所有頂點)是一個常數，所以du=du'，即T中的頂點度數相等。所以:

反之，當G為正則偶圖時，由引理2，3易證式(3)中等式成立。

2 注記和圖例

一般來說，本文得到的上界式(3)與前面所提及的已知上界估計式在一般情況下是不可比較的。Zhang在文獻[4]中指出式(2)總優(yōu)于式(1)。下面通過圖1來說明本文得到的新上界式(3)在某些情況下優(yōu)于式(2)。各上界值如表1所示。

圖1 λ1(G1)上界比較圖Fig.1 A comparative graph of the upper bound of λ1(G1)

表1 λ1(G1)上界的值Tab.1 The values of the upper bound of λ1(G1)

[1]MERRIS R.A Survey of graph Laplacians[J].Linear and Multilinear Algebra，1995，39(3):19-31.

[2]姜譽，方濱興.大型ISP網絡拓撲多點測量及其特征分析實例[J].軟件學報，2005，16(5):846-856.

[3]LI J S，PAN Y L.De Caens inequality and bounds on the largest Laplacian eigenvalue of a graph[J].Linear Algebra Appl，2001，328(4):153-160.

[4]ZHANG X D.Two sharp upper bounds for the Laplacian eigenvalues[J].Linear Algebra Appl，2004，376(3):207-213.

[5]邦迪J A.圖論及其應用[M].北京:科學出版社，1984.

[6]HORN R A，JOHNSON C R.Matrix Analysis[M].New York:Cambridge University Press，1985.

[7]PAN Y L.Sharp upper bounds for the Laplacian graph eigenvalues[J].Linear Algebra Appl，2002，355(2):287-295.

[8]LIU H Q，LU M，TIAN F.On the Laplacian spectral radius of a graph[J].Linear Algebra Appl，2004，376(4):135-141.

[9]張海霞，魏海燕.按樹的最大Laplace特征值對樹進行排序[J].太原科技大學學報，2009，30(6):523-527.

[10]張海霞，謝秀梅.關于樹的Laplace特征值上界的估計[J].太原科技大學學報，2007，28(3):205-207.

[11]張海霞，薛海連.對圖的最大Laplace特征值上界估計的兩個新結果[J].太原科技大學學報，2007，28(1):60-63.