泛圈圖的譜條件

汪 健，王禮想，夏祥偉，于 濤

(安慶師范大學數(shù)學與計算科學學院，安徽安慶 246133)

設G=(V,E)是一個n個頂點m條邊的圖，如果G中邊是沒有方向的，而且G中無環(huán)無重邊以及任意兩點都存在一條路，則稱G為簡單無向連通圖。本文討論的圖都是簡單無向連通圖。設G是一個由頂點集V(G)={v1,v2,…,vn}和邊集E(G)={e1,e2,…,en}構(gòu)成的圖。對于任意的vi∈V(G)，我們用d(vi)或者di表示vi的度，記δ為G的頂點的最小度。若一個圖的頂點集可以劃分為兩個非空子集X和Y，而且該圖的每條邊都有一個端點在X中，另一個端點在Y中，則稱這樣的圖為二部圖。在圖G中，如果對于每一個k(3≤k≤n)，都含有長度為k的圈Ck，則稱G為泛圈圖。圖G的鄰接矩陣A(G)=(aij)n×n定義為：如果vi和vj相鄰，則aij=1，否則aij=0。用μ(G)來表示A(G)的最大特征值，稱為譜半徑。令D(G)為G的度對角矩陣，稱矩陣Q(G)=D(G)+A(G)是G的無符號拉普拉斯矩陣，用q(G)來表示G的無符號拉普拉斯譜半徑。如果G中每對頂點都有一條邊連接，則稱它為完全圖，記作Kn。用Kn-1+v來表示一個有n-1個頂點的完全圖加上一個孤立點。我們用G∨H來表示G和H的連圖，它是通過把G中的每個頂點和H中的每個頂點連接起來所獲得的。

1 相關(guān)引理

引理1[4]設G是一個n階簡單圖(n≥3) ，對應的一個度序列是d1≤d2≤…≤dn，如果存在整數(shù)k滿足dk≤k＜時，有≥n-k。則G是一個泛圈圖或二部圖。

設NPC是K4∨5K1，K2∨(K3+2K1) ，K3∨4K1，K1,2∨4K1，K2∨(K1+K1,3)，K2∨(K2+2K1) ，K1∨2K2，K2∨3K1這些圖的集合。顯然，這些圖是非泛圈的。

引理2設G是一個圖，δ≥2，如果m＞，則G是一個泛圈圖，除非G是一個二部圖或G∈NPC。

證明：設G有n個頂點和m條邊，滿足δ≥2。設d1≤d2≤…≤dn是它的度序列。假設G是一個非泛圈圖且非二部圖，由引理1可知，如果整數(shù)k滿足dk≤k＜時，有dn-k≤n-k-1。則

這里的f(k)=3k2+(1-2n)k+3n-6。因為n＞2k≥2dk≥2δ≥4，所以n≥5，k≥2。又因為，所以f(k) ＞0。

當2≤k＜k1時，得到

2n-13＞。然后可知n＜8。

對于n為偶數(shù)時，同樣地可以得到2＜n＜8。所以n的取值只能為9，7，6，5。

n=9時，有k∈{2,3,4}。因為f(2)=-1，f(3)=-2，f(4)=1，而f(k)＞0，所以k=4。這時，d4≤4，d5≤4。又因為=2m≤52，所以=52即在不等式(1)中等號成立。此時G的度序列是(4,4,4,4,4,8,8,8,8) 。因此G?K4∨5K1。

n=7時，有k∈{2,3}。得到f(2)=1，f(3)=3。如果k=2，根據(jù)定理條件我們知道

n=6時，有k=2 ，而18＜=2m≤20，所以=20即在不等式(1)中等號成立。此時G的度序列是(2,2,3,3,5,5,)，因此G?K2∨(K2+2K1)。

n=5時，有k=2，而11＜=2m≤14，所以=12或14。由于d2≤2，d3≤2，有三個度序列與G對應。(2,2,2,2,4)，此時G?K1∨2K2;(2,2,2,3,3)，此 時 G?K2,3;(2,2,2,4,4)，此時G?K2∨3K1。注意到G?K2,3是二部圖，且G?K2∨(K2+K1,2)是泛圈圖，與前提假設矛盾。

綜上所述，定理證明結(jié)束。

引理3[5]設G是一個n階m條邊的連通圖，則，等號成立時當且僅當G是K1,n-1或Kn。

引理4[6]設G是一個n階m條邊的圖，則。如果G是連通的，則等號成立時當且僅當G是K1,n-1或Kn。如果G不是連通的，等號成立時當且僅當G是Kn-1+v。

2 主要結(jié)論

定理1設G是一個頂點數(shù)n≥5的連通圖，δ≥2。如果，則G是泛圈圖除非G是二部圖或。

證明：假設G是有m條邊的非泛圈圖。我們?nèi)菀装l(fā)現(xiàn)Kn是泛圈的，而δ(K1,n-1)=1，不滿足δ≥2的條件。所以由引理2，我們可知，又因為定理條件要求，所以，解不等式后我們可以得到。再根據(jù)引理1，得出G是一個二部圖或G∈NPC。通過直接計算(見表一)可以知道除了K3∨4K1，K2∨(K2+2K1)，K1∨2K2和K2∨3K1滿足，NPC中其余的圖的μ(G)都是小于。定理證明完成。

定理2設G是一個頂點數(shù)n≥5的圖，δ≥2。如果q(G)≥2n-5+，則G是泛圈圖除非G是二部圖或G∈{K3∨4K1,K2∨3K1}。

證明：假設G是有m條邊的非泛圈圖。我們?nèi)菀装l(fā)現(xiàn)Kn是泛圈的，而δ(K1,n-1)=1，δ(Kn-1+v)=0，不滿足δ≥2此條件。所以由引理3，我們可知。又因為，所以，解不等式后我們可以得到。再根據(jù)引理1，得出G是一個二部圖或G∈NPC。通過直接計算可以知道除了K3∨4K1和K2∨3K1滿足q(G)＞2n-5+，NPC中其余的圖的q(G)都是小于2n-5+。定理證明完成。