圖的最大拉普拉斯特征值的上界

喬曉云

(山西大學(xué)商務(wù)學(xué)院理學(xué)系，太原030031)

設(shè)G=(V，E)是n階簡單圖，其頂點集為V(G)={ν1，ν2，…，νn}，dG(νi)為頂點 νi在圖G中的度數(shù)，簡記為dνi，并假定對頂點進行適當(dāng)排序使得度序列滿足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，從而可以假設(shè)它的特征值為:λ1(G)≥λ2(G)≥…λn(G)=0，其中λ1(G)稱為圖G的最大拉普拉斯特征值。研究拉普拉斯矩陣的特征值有著重要的理論和實際意義，它在計算機網(wǎng)絡(luò)、物理、化學(xué)和生物中有著廣泛而重要的應(yīng)用[1-2]，因而一直受到關(guān)注。近年來關(guān)于拉普拉斯特征值的研究，特別是最大拉普拉斯特征值的上界的估計有了不少代表性的結(jié)果。

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

其中等式成立當(dāng)且僅當(dāng)G為正則偶圖。

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

其中等式成立當(dāng)且僅當(dāng)G為正則偶圖或半正則偶圖。

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

1 引理和主要結(jié)果

設(shè)K(G)=D(G)+A(G)，稱為G的擬拉普拉斯矩陣.熟知當(dāng)G是連通圖時，K(G)是非負，實對稱和不可約矩陣。記ρ(K)是K(G)的譜半徑。

引理1[6]設(shè)M為非負不可約矩陣，ρ(M)為M的譜半徑，則存在一個正特征向量X使得MX=ρ(M)X.

引理 2[7]設(shè)G=(V，E)是n階連通圖，則λ1(G)≤ρ(K)，其中等式成立當(dāng)且僅當(dāng)G是偶圖。

引理3[8]設(shè)G=(V，E)為r正則圖，則 ρ(K)=2r.

定理1 設(shè)G是簡單連通圖，則有:

其中等式成立當(dāng)且僅當(dāng)G為正則偶圖。

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

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

由Cauchy-Schwarz不等式可知:

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

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

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

反之，當(dāng)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網(wǎng)絡(luò)拓撲多點測量及其特征分析實例[J].軟件學(xué)報，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.圖論及其應(yīng)用[M].北京:科學(xué)出版社，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].太原科技大學(xué)學(xué)報，2009，30(6):523-527.

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

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