圖譜半徑的可達(dá)上界與可達(dá)下界

房啟明, 左連翠

(天津師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 天津 300387)

1 圖譜半徑可達(dá)上界與可達(dá)下界的討論

本文所討論的圖均為連通的簡(jiǎn)單圖。

給定一個(gè)n點(diǎn)簡(jiǎn)單圖G=(V,E)，V={v1,v2,…,vn}，d1≥d2≥…≥dn為圖G的度序列，|E|表示圖G中邊的條數(shù)。設(shè)圖G的鄰接矩陣為A(G)=(aij)n×n，其中aij為vi與vj之間邊的條數(shù)，用i～j表示vi與vj相鄰，此時(shí)aij=1；如果vi與vj不相鄰，那么aij=0。A(G)的特征值稱為圖G的特征值。圖G的所有特征值組成的集合即為圖G的譜。圖G的最大特征值即為圖G的譜半徑。將A(G)的特征值按照非增序列排序，得到λ1≥λ2≥…≥λn，其中λ1為圖G的譜半徑，而{λ1,λ2,…,λn}稱為圖G的譜。

圖G的度對(duì)角矩陣為D(G)=diag(d1,d2,…,dn)，其中d1≥d2≥…≥dn。圖G的拉普拉斯矩陣L(G)定義為L(zhǎng)(G)=D(G)-A(G)，而L(G)的特征值稱為圖G的拉普拉斯特征值，圖G的拉普拉斯譜由所有的拉普拉斯特征值構(gòu)成。

圖G的擬拉普拉斯矩陣Q(G)定義為Q(G)=D(G)+A(G)，而Q(G)的特征值稱為圖G的擬拉普拉斯特征值，圖G的擬拉普拉斯譜由所有的擬拉普拉斯特征值構(gòu)成。

文中未說(shuō)明的術(shù)語(yǔ)和符號(hào)參見(jiàn)文獻(xiàn)[1-3]。

圖G的鄰接矩陣的最大特征值λ1即為圖G的譜半徑。文獻(xiàn)[4]給出了圖的擬拉普拉斯譜半徑的一個(gè)可達(dá)上界

圖的譜半徑、圖的拉普拉斯譜半徑與圖的擬拉普拉斯譜半徑之間也存在著聯(lián)系，參考文獻(xiàn)[5-7]主要討論了它們之間的大小關(guān)系，其中文獻(xiàn)[7]得到以下結(jié)論:

2λ1≤q1，

(1)

嘗試給出λ1的一個(gè)可達(dá)上界，使得當(dāng)q1達(dá)到其上界時(shí)，λ1同樣達(dá)到其上界。在此基礎(chǔ)上，給出λ1的一個(gè)可達(dá)下界。最后，將得到的上界、下界和引理3與引理4中的上界、下界進(jìn)行比較，并證明在一定條件下得到的上界和下界更好。

2 主要結(jié)論及證明

定義1[4]設(shè)連通的簡(jiǎn)單圖H=(V,E)有n個(gè)頂點(diǎn)，且滿足V(H)={v1}∪V1∪V2。設(shè)d1=Δ1，V1={vk|k～1,dk=δ},V2={vk|vk與v1不相鄰，dk=Δ2}，其中Δ1，Δ2，δ滿足Δ1=Δ2(1+Δ2-δ)。Ψ為所有滿足上述條件的圖H所構(gòu)成的集合。

定義2[4]如果一個(gè)簡(jiǎn)單圖有一個(gè)n-1度點(diǎn)，其余的點(diǎn)的度數(shù)均為Δ2<(n-1)，則稱這樣的圖為(n-1,Δ2)半正則圖。Φ為所有滿足上述條件的圖所構(gòu)成的集合。

引理1[8]設(shè)M是非負(fù)不可約矩陣，ρ(M)是其譜半徑，則有結(jié)論:

(1)M有一正實(shí)特征值恰好等于它的譜半徑ρ(M)；

(2)存在一個(gè)正向量X使得MX=ρ(M)X；

(3)當(dāng)M的任意元素(一個(gè)或多個(gè))增加時(shí)，其譜半徑不減少。

引理2[4]設(shè)連通圖G的度序列為d1≥d2≥…≥dn，則其擬拉普拉斯矩陣的最大特征值滿足

當(dāng)且僅當(dāng)G是正則圖或G∈Ψ或G∈Φ時(shí)，等號(hào)成立。

引理3[9]設(shè)圖G為具有n個(gè)頂點(diǎn)的簡(jiǎn)單連通圖，不妨設(shè)其頂點(diǎn)度序列滿足d1≥d2≥…≥dn，則

對(duì)于任意的1≤l≤n都成立。

進(jìn)一步，當(dāng)l=1時(shí)，等式成立當(dāng)且僅當(dāng)G是正則圖；當(dāng)2≤l≤n時(shí)，等式成立當(dāng)且僅當(dāng)G為滿足d1=d2=…=dl-1=n-1，dl=dl+1=…=dn=η的二度圖。

引理4[10]設(shè)圖G為具有n個(gè)頂點(diǎn)的簡(jiǎn)單連通圖，不妨設(shè)其頂點(diǎn)度序列滿足d1≥d2≥…≥dn，則

當(dāng)且僅當(dāng)G是正則圖時(shí)，等式成立。

定理1 設(shè)連通圖G的度序列為d1≥d2≥…≥dn，則

(2)

當(dāng)且僅當(dāng)G是正則圖或G∈Ψ或G∈Φ時(shí)，等號(hào)成立。

由于A(G)X=λ1X，那么對(duì)于第i行，有

(3)

所以，對(duì)于第j行，有

從而

(λ1-dj+1)xj≤1,

(4)

(3)與(4)式兩端分別相乘，再消去xj,得

λ12-(dj-1)λ1-di≤0,

那么，根據(jù)λ1是正的特點(diǎn)可得

下證

若想讓(2)式中等號(hào)成立，則(3)、(4)兩式中等號(hào)必須成立，因此

(5)

(6)

且當(dāng)(4)式中等號(hào)成立時(shí)，一定有i～j。

設(shè)V0={vk|xk=xj}。假設(shè)V0≠V{vi}，則存在vp與vq，使得p～q，vp∈V0,vqV0且vq≠vi。因?yàn)閤j為第二大的分量，且xp=xj，所以xq

若xj=1，此時(shí)λ1=di(i=1,2,…,n)，因此圖G中所有點(diǎn)的度數(shù)均相同，為正則圖。此時(shí)(2)式中等號(hào)成立。即

若xj≠1，此時(shí)分兩種情況討論。

情況1di=n-1。

情況2di

設(shè)V1={vk|k～i}，V2={vk|vk與vi不相鄰}。則由(3)式可得

λ1=dixj，

(7)

即

若vj∈V1，由(4)式可得

(8)

即

若vk∈V2，由(6)式，易得

λ1xk=dkxk，

(9)

即

λ1=dk,

亦即

設(shè)Δ1=di,δ=dj,Δ2=dk。聯(lián)立(7)、(8)、(9)三式,可得

Δ1=Δ2(1+Δ2-δ),

且有Δ1>Δ2>δ，所以G∈Ψ。

由(7)、(8)兩式，易得di≥dj。(7)、(8)兩式相乘,并消去xj，得

綜上所述，得出

僅當(dāng)G是正則圖或G∈Ψ或G∈Φ時(shí)，等號(hào)成立。

反之，推出當(dāng)G是正則圖或G∈Ψ或G∈Φ時(shí)，(2)式等號(hào)成立。此定理得證。

推論1λ1≤n-1。

證明由定理1容易得出，

推論2 設(shè)圖G的度序列為d1≥d2≥…≥dn，則λ1≥dn。

證明設(shè)正則圖G′的度序列為{d1,d2,…，dn}，則由定理1，正則圖G′的譜半徑為dn。由引理1，當(dāng)G′中的任意頂點(diǎn)的度(一個(gè)或多個(gè))增加時(shí)，其譜半徑不減少,因此有λ1≥dn。

對(duì)比定理1與引理2，當(dāng)G是正則圖，G∈Ψ或G∈Φ時(shí)，G的譜半徑λ1與G的擬拉普拉斯矩陣的譜半徑q1同時(shí)取到最大值。并且當(dāng)G為正則圖時(shí)，(1)式取等號(hào)，此時(shí)有2λ1=q1。

討論圖G的譜半徑的一個(gè)可達(dá)下界。

定理2 設(shè)連通圖G的度序列為d1≥d2≥…≥dn，則

(10)

當(dāng)且僅當(dāng)G是正則圖或G∈Φ時(shí)，等號(hào)成立。

由于A(G)X=λ1X，對(duì)于第p行，有

(11)

對(duì)于第q行，有

即

(λ1-dq+1)xq≥1。

(12)

(11)式與(12)式兩端分別相乘，再消去xq，得

λ12-(dq-1)λ1-dp≥0,

因此

(13)

如果(13)式中等號(hào)成立，則(11)、(12)兩式中等號(hào)必然成立。當(dāng)(12)式中等號(hào)成立時(shí)，必然有p～q，因此

結(jié)合定理1，得到

綜上所述，(10)式得證。

當(dāng)G∈Ψ時(shí)，很容易舉出反例，使得

圖1 圖G

此時(shí)(10)式中的等式無(wú)法成立。例如Δ1=6，δ=2，Δ2=3，則圖G如圖1所示。此時(shí)

顯然二者不相等。

當(dāng)圖G為k-正則圖或G∈Φ時(shí)，易得

此時(shí)(10)式中的等式成立,即

將定理1與引理3的結(jié)論相比較得到，

顯然，在一定條件下，定理1的結(jié)論優(yōu)于引理3。并且，僅在兩種極其特殊的情形下，引理3中的等式才成立；而定理1中等式成立的情況更多，涵蓋范圍更廣(例如G∈Ψ時(shí)，定理1中等式成立，而引理3中等式不成立)。因此，上述得到的上界更好。

將定理2與引理4的結(jié)論相比較。

情況1 設(shè)樹(shù)圖G的度序列為d1≥d2≥…≥dr≥dr+1≥…≥dn。設(shè)dr+1=dr+2=…=dn=1，且dr>1。如果圖G中的第二小度點(diǎn)的度數(shù)大于等于4，即dr≥4，則由定理2得，

由引理4得，

在這種情況下，定理2優(yōu)于引理4。

由引理4得

情況3 當(dāng)G∈Φ時(shí)，定理2等式成立，引理4中等式不成立，在這種情況下，定理2優(yōu)于引理4。

由此可見(jiàn),定理2在一些情況下優(yōu)于引理4，所以在使用時(shí)要視情況而定。

[參考文獻(xiàn)]

[1] BONDY J A, MURTY U S R. Graph theory with applications[M]. New York: Macmillan Press,1976:1-24.

[2] 程云鵬.矩陣論[M].4版.西安:西北工業(yè)大學(xué)出版社,2013:234-288.

[3] MOHAR B. On the sum ofklargest eigenvalues of graphs and symmetric matrice[J].Preprint series,2008(46):306-313.

[4] A Dilek (Güng?r) Maden, KINKAR Ch Das, A Sinan Cevik. Sharp upper bounds on the spectral radius of the signless Laplacian matrix of a graph[J].Applied Mathematics and Computation,2013(219):5025-5032.

[5] SHU Jin-long, HONG Yuan, WEN Ren-kai. A sharp upper bound on the largest eigenvalue of the Laplacian matrix of a graph[J].Linear Algebra and its Applications,2002(347):123-129.

[6] 譚尚旺，郭紀(jì)明，亓健.圖的Laplacian矩陣和擬-Laplacian矩陣的譜半徑[J].工程數(shù)學(xué)學(xué)報(bào)，2003,20(6):69-74.

[7] CHEN Yan.Properties of spectra of graphs and line graphs[J].Applied Mathematics a Journal of Chinese Universities, B,2002,17(3):371-376.

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

[9] SHU Jin-long, WU Ya-rong. Sharp upper bounds on the spectral radius of graphs[J]. Linear Algebra and its Applications,2004(377):241-248.

[10] VARGA R S. Matrix iterative analysis[M]. New Jersey: Prentice-Hall Engelwood Cliffe,1962.