房啟明, 左連翠

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

1 圖譜半徑可達上界與可達下界的討論

本文所討論的圖均為連通的簡單圖。

給定一個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相鄰，此時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的度對角矩陣為D(G)=diag(d1,d2,…,dn)，其中d1≥d2≥…≥dn。圖G的拉普拉斯矩陣L(G)定義為L(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)成。

文中未說明的術(shù)語和符號參見文獻[1-3]。

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

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

2λ1≤q1，

(1)

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

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

定義1[4]設(shè)連通的簡單圖H=(V,E)有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]如果一個簡單圖有一個n-1度點，其余的點的度數(shù)均為Δ2<(n-1)，則稱這樣的圖為(n-1,Δ2)半正則圖。Φ為所有滿足上述條件的圖所構(gòu)成的集合。

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

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

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

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

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

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

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

對于任意的1≤l≤n都成立。

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

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

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

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

(2)

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

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

(3)

所以，對于第j行，有

從而

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

(4)

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

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

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

下證

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

(5)

(6)

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

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

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

若xj≠1，此時分兩種情況討論。

情況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∈Φ時，等號成立。

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

推論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′中的任意頂點的度(一個或多個)增加時，其譜半徑不減少,因此有λ1≥dn。

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

討論圖G的譜半徑的一個可達下界。

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

(10)

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

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

(11)

對于第q行，有

即

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

(12)

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

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

因此

(13)

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

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

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

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

圖1 圖G

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

顯然二者不相等。

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

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

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

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

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

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

由引理4得，

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

由引理4得

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

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

[參考文獻]

[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] 譚尚旺，郭紀明，亓健.圖的Laplacian矩陣和擬-Laplacian矩陣的譜半徑[J].工程數(shù)學(xué)學(xué)報，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.