非正則k-連通圖的譜半徑

賈會才，王志偉

(河南工程學(xué)院 數(shù)理科學(xué)系，河南 鄭州 451191)

給定n-階k-連通圖G，其頂點集V(G)={v1,v2,…,vn}， 邊集E(G)={e1,e2, …，em}，Δ為其最大度，δ為其最小度，且度序列為Δ=d1≥d2≥…≥dn=δ.設(shè)A(G)是圖G的鄰接矩陣，則A(G)是n階非負(fù)不可約的實對稱矩陣，那么A(G)的特征值全為實數(shù)，不妨設(shè)為λ1≥λ2≥…≥λn，我們稱λ1為圖G的譜半徑，記作ρ(G).近年來，對譜半徑的上下界的研究已經(jīng)有大量的文獻(xiàn)存在[1]，研究譜半徑一直是圖譜理論中一個重要的課題.我們知道，對正則連通圖，顯然ρ(G)=Δ， 而對非正則連通圖，ρ(G)<Δ，那么一個很直接的問題就產(chǎn)生了，此時二者到底相差多少？即Δ-ρ(G)的下界問題.對一般的連通非正則圖，這個問題已經(jīng)得到了充分的研究[2-6]，在這些文獻(xiàn)中，作者通過越來越細(xì)致的分析，得到了一系列逐步精確的下界.本文通過研究k-連通非正則圖的結(jié)構(gòu)特點，利用柯西-施瓦茲不等式作為工具，從而得到了一個很好的下界.

一個圖G被說成是k-連通的，如果它的點連通度大于等于k.設(shè)圖G是n階k-連通圖，對任意的u,ν∈V(G),點u與點v之間的距離記為dG(u，v).圖G的直徑D是指G中任意兩點之間的最大距離.設(shè)A(G)是圖G的鄰接矩陣，則A(G)是n階非負(fù)不可約的實對稱矩陣，那么A(G)的特征值全為實數(shù)，不妨設(shè)為λ1≥λ2≥…≥λn，我們稱λ1為圖G的譜半徑，記作ρ(G).由著名的Perron-Frobenius定理知，有唯一一個正的單位特征向量X對應(yīng)于ρ(G)，通常稱X為圖G的Perron向量.

對一般的連通非正則圖G，關(guān)于Δ-ρ(G)的下界已經(jīng)有下面的結(jié)果：

(1) 2004年Dragan Stevanovic給出了

(2) 2005年Xiao-Dong Zhang證明了

(3) 2007年Bolian Liu等證明了

(4) 2007年Sebastian M.Cioaba等給出了

基于上述已知結(jié)果，該文將此問題推廣到非正則k-連通圖，并提供了Δ-ρ(G)的一個精確的下界.

1 主要結(jié)果證明

定理如果G是n-階非正則k-連通圖，那么

證明：令X是A的對應(yīng)于譜半徑ρ的Perron向量，E為圖G的邊集.對每一個i∈[n]={1，2，…，n}，令di為G的頂點i的度，那么

于是

min {l1，l2，…，lk}≤D.

考慮到

因為

所以

證畢.

2 結(jié) 論

本文主要研究了k-連通非正則圖G，其最大度與譜半徑差值的一個下界.關(guān)于下界的改進(jìn)問題，有待進(jìn)一步研究.

參考文獻(xiàn)：

[1] CVETKOVIC D M,DOOB M,SACHS H. Spectra of graphs[M]. Johann Ambrosius Barth Verlag,1995.

[2] STEVANOVIC D. The largest eigenvalue of non-regular graphs[J]. J. Combin. Theory Ser. B, 2004,(91):143-146.

[3] ZHANG X D.Eigenvectors and eigenvalues of non-regular graphs[J]. Linear Algebra Appl,2005,(409):79-86.

[4] LIU B L,SHENG J,WANG X M. On the largest eigen value of non-regular graphs[J]. J. Combin. Theory Ser. B, 2007,(97):1 010-1 018.

[5] CIOABA S M,GREGORY D A,NIKIFOROV V. Extreme eigenvalues of non-regular graphs[J]. J. Combin. Theory Ser. B, 2007,(97):483-486.

[6] CIOABA S M. The spectral radius and the maximal degree of irregular graphs [J]. The Electronic Journal of Combinatorics,2007,(14):1-10.