一類圖的譜

曾建宇，何常香

（上海理工大學(xué) 理學(xué)院，上海 200093）

1 基本概念及背景介紹

圖的譜可以反映出圖的許多性質(zhì)，圖以上3 種特征值都是圖的同構(gòu)不變量。完全圖又是圖論中一類基礎(chǔ)而重要的圖，其結(jié)構(gòu)的特殊性導(dǎo)致了它的研究方法的差異性及其結(jié)果的簡潔性。Bergstrand 等[1]和Hartsfield 等[2]分 別 在1986 年 和1992 年對完全圖和完全二部圖進(jìn)行研究并得到一些結(jié)論[1-2]。同時文獻(xiàn)[3]也得到一些關(guān)于連通圖譜半徑的結(jié)論。本文主要研究特殊圖類Hn,Km的各種譜，Hn,Km是對書圖的一個推廣。對于一個給定的圖類，確定該圖類中圖的鄰接譜半徑的上界并刻畫達(dá)到該上界的圖，這是Brualdi 和Solheid 在1986 年提出的關(guān)于圖的譜半徑的一個問題[4]。此后，這些問題得到廣泛研究，被稱為Brualdi-Solheid問題。關(guān)于圖的Brualdi-Solheid 問題的研究對于研究圖的特性有著重要意義，文獻(xiàn)[5-7]按照鄰接譜半徑對某些圖類進(jìn)行了排序，其中文獻(xiàn)[7]首先找到了具有給定匹配數(shù)的雙圈圖的最大鄰接譜半徑。

同時，Brualdi-Solheid 問題也被移植到圖的拉普拉斯譜半徑和無符號拉普拉斯譜半徑研究中。文獻(xiàn)[8]利用樹的階數(shù)給出了樹的Laplacian 矩陣的最大特征值的分布；文獻(xiàn)[9]利用階數(shù)給出了 n階單圈圖的Laplacian 矩陣的最大特征值的第一、第二、第三、第四大值及最小值。此外，對具有固定不變量的圖的譜半徑也有一些研究結(jié)果。特別是在文獻(xiàn)[10-11]中，分別討論了具有固定最大度的 n個頂點上的樹和單圈圖的譜半徑。

本文計算鄰接矩陣、拉普拉斯矩陣和無符號拉普拉斯矩陣的特征值，考慮在頂點數(shù)N=m(n+1)固定的情況下，給出了鄰接譜半徑的上界和拉普拉斯、無符號拉普拉斯譜半徑的上下界，并刻畫了達(dá)到上下界的極圖。

定義1 設(shè) Km是m階完全圖，取n+1個Km，將其中一個Km（主圖）的第i個頂點分別和其余的n個Km（輔圖）的第i個頂點相連（i =1,2,···,n），所得到的(mn+m)階完全關(guān)聯(lián)圖記為Hn,Km，其中n ≥2，m ≥2。

例如，書圖H4,K2和12 階完全關(guān)聯(lián)圖H3,K3分別如圖1 和圖2 所示。

圖 1 書圖 H4,K2Fig. 1 Book graph H4,K2

圖 2 完全關(guān)聯(lián)圖H3,K3Fig. 2 Complete associated graph H3,K3

從定義不難看出Hn,Km鄰接矩陣和度對角矩陣分別為

式中， Em表 示 m階 單位矩陣。

故 Hn,Km的拉普拉斯和無符號拉普拉斯矩陣分別為

定義2[12]設(shè) M為實對稱矩陣，將其行列作相同的劃分，其每一子塊的平均行和作為元素按其子塊的位置順序構(gòu)成的矩陣稱為 M的商矩陣。

定義3[12]給定圖 G，設(shè)V1,V2,···,Vk是V(G)的一個劃分，若對任意i,j ∈{1,2,···,k}，Vi中的每一個點在 Vj中都有相同個數(shù)的鄰點，則稱V1,V2,···,Vk為均勻劃分。

引理1[12]對于一個均勻劃分，若 v是商矩陣B 對應(yīng)特征值 λ的一個特征向量，則 Sv是實對稱矩陣 M的對應(yīng)特征值 λ的一個特征向量，其中 S為M的特征矩陣。

由引理1 顯然可知，對于實對稱矩陣 M，其商矩陣B 的特征值都是 M的特征值。

推論1 對于圖 G的鄰接矩陣A(G)，其任何商矩陣的特征值都是A(G)的特征值。

證明 設(shè)A(G)是圖 G的鄰接矩陣，SA是圖G的一個商矩陣，S′A是SA的一個商矩陣。由引理1可知，SA的特征值一定是A(G)的特征值，同理 S′A的特征值一定是 SA的特征值。所以，S′A的特征值都是A(G)的特征值。

與推論1 同理，可得到推論2。

推論2 對于圖 G的拉普拉斯矩陣L(G)和無符號拉普拉斯矩陣Q(G)，它們?nèi)魏紊叹仃嚨奶卣髦刀际荓(G) 和 Q (G)的特征值。

商矩陣和均勻劃分都是計算證明譜的關(guān)鍵工具。在推論3 中，定義均勻劃分并進(jìn)行證明。

推論3 設(shè)Hn,Km的頂點集合為，其中v1,···,vm是主圖的頂點，是第 k 個 輔圖頂點n)。則是Hn,Km的一個均勻劃分。

從圖Hn,Km的結(jié)構(gòu)可知：當(dāng)vi∈Vi，其中i∈{1,2,···,m}時，vi在 其所在的頂點集 Vi中沒有鄰點；在頂點集 Vk中 有且僅有1 個鄰點，其中k ∈{1,2,···,m}且k ≠i；在頂點集Vm+l中沒有鄰點，其中l(wèi) ∈{1,2,···,m} 且l ≠i；在頂點集Vm+l中有 n個鄰點，其中l(wèi) ∈{1,2,···,m}且l =i。

當(dāng)vik∈Vm+k， 其中 i∈{1,2,···,n}，k ∈{1,2,···,m}時， vik在頂點集 Vl中有且僅有1 個鄰點，其中l(wèi)=k； vik在其他剩余的所有頂點集中都沒有鄰點。

綜上，均勻劃分得證。

2H n,Km的各種譜

定理1 主要計算Hn,Km的鄰接譜。在證明過程中，主要利用了商矩陣和矩陣秩的相關(guān)結(jié)論。

定理1 圖Hn,Km的鄰接譜為，其中n≥2,m≥2。

1(m-1)×mO(m-1)×m(m-1)×m

λ=-1 A(Hn,Km)(m-1)(n-1)

式中： 為元素全為1 的 階矩陣； 為全1 的重向量；和分別為階全1 和全0 矩陣。綜上可知是的重特征值。

設(shè)B2=(m-1)E-A(Hn,Km)，則

令C=(1-m)Em+A(Km)，因為

所以R(B2)=(n+1)m-(n-1) 。綜上可知λ=m-1是A(Hn,Km) 的n -1重特征值。

由引理1 可知，商矩陣SAm的特征值即為A(Hn,Km)的特征值。

利用定理1 同樣的計算證明方法，可得到Hn,Km的拉普拉斯和無符號拉普拉斯譜。

定理2Hn,Km的拉普拉斯和無符號拉普拉斯譜分別為

其中， n≥2,m ≥2。

3H n,Km 的譜半徑

對于圖Hn,Km可知其頂點數(shù)為N=m(n+1)，定義Hn,Km表 示所有點數(shù)為 N的圖構(gòu)成的集合。本文考慮當(dāng) N固定時，對圖鄰接譜半徑的最大值和拉普拉斯和無符號拉普拉斯譜半徑的最大和最小值分別進(jìn)行計算證明。

定理3 設(shè)N=m(n+1)為固定值，且n≥2, m≥2。則對于任意 G∈Hn,Km，，等號成立當(dāng)且僅當(dāng)G=H2,K[N/3]。

證明 令f1=λ(G)，由定理1 中任一圖的鄰接譜可知， 其中n ≥2,m ≥2。因為N=m(n+1)，所以可知n與m成反比。假設(shè)m=n，則，所以可知當(dāng)n=2時，λ(G)達(dá)到上界，此時極圖為G=H2,K[N/3]。

定理4 設(shè)N=m(n+1)為固定值，且n≥2, m≥2，則對于任意G∈Hn,Km，，右邊等號成立當(dāng)且僅當(dāng)G=Hm,Km，左邊等號成立當(dāng)且僅當(dāng)G=H2,K[N/3]或G=H[N/3],K2。

與前兩定理證明類似，下面研究對于任意G ∈Hn,Km，當(dāng)其無符號拉普拉斯譜半徑達(dá)到上界時的極圖。

定理5 設(shè)N=m(n+1)為固定值，且n≥2,m ≥2。則對于任意，右邊等號成立當(dāng)且僅當(dāng) G =H2,K[N/3]，左邊等號成立當(dāng)且僅當(dāng)G=Hm,K2m-1。