僅有三個非負(fù)特征值的圖

糟玉英，王國平

(1.新疆工程學(xué)院數(shù)理學(xué)院，烏魯木齊 830029；2.新疆師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，烏魯木齊 830017)

本文考慮的圖皆為簡單無向圖.設(shè)圖G的點集為V(G)={v1，v2，… ，vn}.用A(G)=(aij)n×n來表示圖G的鄰接矩陣，其中，若vi和vj相鄰則aij=1，否則aij=0.因為是實對稱的，所以A(G)可以將其特征值設(shè)為λ1(G)≥λ2(G)≥…≥λn(G).A(G)的特征值也稱為圖G的特征值，由G的所有特征值構(gòu)成的集合被稱為圖G的譜．

關(guān)于圖的譜的研究結(jié)果有很多.文獻(xiàn)[1]刻畫了僅有一個特征值小于-1的連通圖.文獻(xiàn)[2]中確定了至多有兩個非負(fù)特征值的簡單圖.文獻(xiàn)[3]確定了至少有6個非零特征值的二部圖.文獻(xiàn)[4]得到了僅有兩個非負(fù)特征值的圖的第三大特征值.文獻(xiàn)[5]描述了恰好有兩個非負(fù)特征值的圖．

設(shè)圖G的邊集和點集分別為E(G)和V(G).若圖G是連通的且其點集和邊集滿足E(G)|=V(G)|-1+c，則稱G為c圈圖.當(dāng)c=0，1，2，3時，G被分別稱為樹、單圈圖、雙圈圖、三圈圖.文獻(xiàn)[6]確定了帶有k個懸掛點的三圈圖中譜半徑最大的圖.文獻(xiàn)[7]刻畫了帶有完美匹配的三圈圖中具有最大特征值的圖.文獻(xiàn)[8]得到了三圈圖中具有最大無符號拉普拉斯譜半徑的圖.文獻(xiàn)[9]刻畫了第二大特征值不超過1的所有三圈圖.文獻(xiàn)[10]刻畫了二部三圈圖中譜半徑最大的圖．

本文首先確定了僅有三個非負(fù)特征值的所有樹、單圈圖、雙圈圖和三圈圖，同時也確定了僅有三個非負(fù)特征值的非連通圖．

1 滿足λ3(G)≥0和λ4(G)<0的連通圖G

設(shè)G是一個連通圖，其頂點集為V(G).讓V′?V(G)，將V′中的點按照原來在G中的鄰接關(guān)系進(jìn)行連接后得到的圖就稱為G的誘導(dǎo)子圖．

引理1[11]設(shè)G是一個n階連通圖，H是G的m階誘導(dǎo)子圖.G和H的特征值分別為λ1(G)≥λ2(G)≥…≥λn(G)和λ1(H)≥λ2(H)≥…≥λn(H).那么當(dāng)1≤i≤m時，λi(G)≥λi(H)≥λn-m+i(G).

引理2[11]設(shè)G是一個二部圖，則其譜是對稱的，即若θ是G的m重特征值，那么-θ也是G的m重特征值．

由引理2易知下列引理3成立．

引理3若T∈T7,則T恰有四個非負(fù)特征值．

用Pn，Sn和Cn分別表示n個點的路，星圖和圈.雙星圖Sa，b是將a和b個點分別連接在P2的兩端后得到的(a+b=n-2).圖H6是將一條邊的端點粘在P5的中間點上后得到的．

定理1設(shè)T∈Tn.若λ3(T)≥0且λ4(T)<0，則T同構(gòu)于下列圖中的一個：

S4，S2，1，P5，P6，H6.

證明明顯地，n≥4.當(dāng)n≥7時，容易觀察到對于Tn中的任一個樹T都含有七個點的子樹T7作為其誘導(dǎo)子圖.根據(jù)引理1及引理3可知，λ4(T)≥λ4(T7)，這表明，T同樣至少有四個非負(fù)特征值.因此，可以認(rèn)為4≤n≤6．

借助Maple計算后容易看出，當(dāng)λ3(T)≥0且λ4(T)<0時，T同構(gòu)于下面五個圖中的一個：S4，S2，1，P5，P6，H6．

用Cn+v表示將一個點與Cn的某個點連接后得到的圖；用C3⊙2表示將兩個點與C3的同一個點連接后得到的圖；用Cn⊕2v表示將兩個點分別與Cn的兩個相鄰點連接后得到的圖；用C3+Pn表示將Pn的一個端點與C3的某個點連接后得到的圖；用C3⊙2P2表示將兩條P2各自的一個端點與C3的同一個點連接后得到的圖；用C3⊕2P2表示將兩條P2各自的一個端點分別與C3的兩個相鄰點連接后得到的圖；用C3⊙v⊙P2表示將一個點及P2的一個端點與C3的同一個點連接后得到的圖；用C3⊕v⊕P2表示將一個點及P2的一個端點分別與C3的兩個相鄰點連接后得到的圖；用C3⊕3v表示將三個點分別與C3的三個點連接后得到的圖；用C3+P3表示將P3的中間點與C3的某個點連接后得到的圖；用C3+P4表示將P4的某個二度點與C3的某個點連接后得到的圖．

Ck(4≤k≤7)，C4+v，C5+v，C3⊙2v，

C3⊕2v，C4⊕2v，C3+P3，C3+P4，

C3⊙2P2，C3⊕2P2，C3⊙v⊙P2，

C3⊕v⊕P2，C3⊕3v，C3+P3，C3+P4.

證明當(dāng)n≥8時，可觀察出G至少含有七個點的樹T7作為其誘導(dǎo)子圖.由引理1及引理3可知，λ4(G)≥λ4(T7)，這表明G至少有四個非負(fù)特征值.明顯地，n≥4，故可確定4≤n≤7．

借助Maple計算得到，當(dāng)λ3(T)≥0且λ4(T)<0時，G同構(gòu)于下列十八個圖中的一個：

Ck(4≤k≤7)，C4+v，C5+v，C3⊙2v，

C3⊕2v，C4⊕2v，C3+P3，C3+P4，C3⊙2P2，C3⊕2P2，C3⊙v⊙P2，

C3⊕v⊕P2，C3⊕3v，C3+P3，C3+P4.

啞鈴圖是將兩個點不交的圈分別粘在一條路的兩個端點后得到的；∞圖是由恰有一個公共點的兩個圈構(gòu)成的；θ圖是將不同的兩個點用三條內(nèi)部不交的路連接起來后得到的，其中三條路中至多有一條路的長度為1.顯然，任一個雙圈圖都是將一些樹粘在啞鈴圖，∞圖或θ圖上得到的.讓bn，θn及∞n分別表示帶有n個點的啞鈴圖，∞圖及θ圖．

用b6+v和b6+P2分別表示將一個點和P2的一個端點與b6的某個二度點連接后得到的圖；用b6⊕v和b6⊕P2分別表示將一個點和P2的一個端點與b6的一個三度點連接后得到的圖.用∞5+v和∞5+P2分別表示將一個點和P2的一個端點與∞5的某個二度點連接后得到的圖；用∞5*v和∞5*P2分別表示將一個點和P2的一個端點與∞5的四度點連接后得到的圖；用∞5+2v表示將兩個點分別與∞5的兩個相鄰二度點連接后得到的圖.用θ4⊙2v，θ4°2v及θ4?2v分別表示將兩個點與θ4中的一個二度點，不同的二度點及相鄰的兩個點連接后得到的圖；用θ4⊙v⊙P2，θ4°v°P2及θ4?v?P2，分別表示將一個點及P2的一個端點與θ4的一個二度點，不同的二度點及相鄰的兩個點連接后得到的圖；用θ4+P2和θ4+P3分別表示將P2和P3的一個端點與θ4的一個二度點連接后得到的圖；用θ4⊕v和θ4⊕P2分別表示將一個點和P2的一個端點與θ4的一個三度點連接后得到的圖．

b6+v，b6+P2，b6⊕v，b6⊕P2，∞5+v，

∞5+P2，∞5*v，∞5*P2，∞5+2v，∞6，

θ4⊙2v，θ4°2v，θ4·2v，θ4⊙v⊙P2，

θ4°v°P2，θ4·v·P2，θ4+P2，

θ4+P3，θ4⊕v，θ4⊕P2，Di(1≤i≤12).

圖1 Di(1≤i≤12)Fig.1 Di(1≤i≤12)

證明利用Maple可計算出λ3(θ4)=-1<0且λ4(θ4)=-1.5616<0.這意味著n≥5.當(dāng)n≥9時，可觀察到G至少含有七個點的樹T7作為其誘導(dǎo)子圖.根據(jù)引理1及引理3可知λ4(G)≥λ4(T7)，這說明G至少有四個特征值是非負(fù)的．

由上所述，可以確定5≤n≤8．

經(jīng)過Maple計算后可以確定，G同構(gòu)于下列32個圖中的一個：

b6+v，b6+P2，b6⊕v，b6⊕P2，∞5+v，

∞5+P2，∞5*v，∞5*P2，∞5+2v，

∞6，θ4⊙2v，θ4°2v，θ4·2v，θ4⊙v⊙P2，

θ4°v°P2，θ4·v·P2，θ4+P2，θ4+P3，

θ4⊕v，θ4⊕P2，Di(1≤i≤12).

用I1⊙2v表示將兩個點與I1⊕P3I1的同一個點連接后得到的圖；用I1?2v表示將兩個點分別與I1的兩個相鄰點連接后得到的圖；用和I1⊕P4分別表示將P3和P4的一個端點與I1的某個點連接后得到的圖；用I1⊙v⊙P2表示將一個點及P2的一個端點與I1的同一個點連接后得到的圖；用I1?v?P2表示將一個點和P2的一個端點分別與I1的兩個相鄰點連接后得到的圖；用I1⊙2P2表示將兩條P2各自的一個端點與I1的同一個點連接后得到的圖；用I1+P3表示將P3的中間點與I1的某個點連接后得到的圖；用I1+P4表示將P4的某個二度點與I1的某個點連接后得到的圖．

用I2+v，I2⊕v及I2*v分別表示將一個點與I2的二度點，三度點及四度點連接后得到的圖；用I2+P2，I2⊕P2及I2*P2分別表示將P2的一個端點與I2的二度點，三度點及四度點連接后得到的圖；用I2°2v表示將兩個點分別與I2的不同二度點連接后得到的圖；用I2?2v表示將兩個點分別與I2的相鄰的二度點和三度點連接后得到的圖．

用I3+v和I3⊕v分別表示將一個點與I3的二度點和與二度點相鄰的三度點連接后得到的圖；用I3?2v表示將兩個點分別與I3的相鄰的二度點和三度點連接后得到的圖；用I4+v表示將一個點與I4的某個二度點連接后得到的圖；用I4°2v表示將兩個點分別與I4的不同二度點連接后得到的圖；用I5+v和I5⊕v分別表示將一個點與I5的二度點和與二度點相鄰的三度點連接后得到的圖．

用I7⊕v表示將一個點與I7的某個三度點連接后得到的圖；用I8+v表示將一個點與I8中四度點和二度點相鄰的二度點連接后得到的圖；用I8⊕v表示將一個點與I8中三度點和二度點相鄰的三度點連接后得到的圖；用I9+v表示將一個點與I9中兩個三度點相鄰的二度點連接后得到的圖．

用I29v表示將一個點與I29中四度點相鄰的二度點連接后得到的圖；用I30+v表示將一個點與I30中兩個三度點相鄰的二度點連接后得到的圖；用I30⊕v表示將一個點與I30中二度點不相鄰的三度點連接后得到的圖；用I31+v表示將一個點與I31中三度點相鄰的二度點連接后得到的圖．

用I32⊕v和I32*v分別表示將一個點與I32的三度點和四度點連接后得到的圖；用I32⊕P2和I32*P2分別表示將P2的一個端點與I32的三度點和四度點連接后得到的圖；用I32+v和I32+P2分別表示將一個點和P2的一個端點與I32中三度點相鄰的二度點連接后得到的圖；用I32v和I32P2分別表示將一個點和P2的一個端點與I32中四度點相鄰的二度點連接后得到的圖．

Ii(3≤i≤31)，I1⊙2v，I1·2v，I1⊕P3，

I1⊕P4，I1⊙v⊙P2，I1·v·P2，I1⊙2P2，I1+P3，
I1+P4，I2+v，I2⊕v，I2*v，I2+P2，

I2⊕P2，I2*P2，I2°2v，I2·2v，I3+v，I3⊕v，
I3·2v，I4+v，I4°2v，I5+v，I5⊕v，I7⊕v，

I8+v，I8⊕v，I9+v，I29v，I30+v，I30⊕v，
I31+v，I32⊕v，I32*v，I32⊕P2，I32*P2，

I32+v，I32+P2，I32v，I32P2.

圖2 Ii(1≤i≤32)Fig.2 Ii(1≤i≤32)

證明若n=4則G?I1.利用Maple計算得出λ2(I1)=λ3(I1)=λ4(I1)=-1<0，這意味著n≥5.當(dāng)n≥10時，可以觀察到G至少含有七個點的樹T7作為其誘導(dǎo)子圖.根據(jù)引理1及引理3得到λ4(G)≥λ4(T7).顯然可知，G的特征值至少有四個是非負(fù)的.因此得出5≤n≤9.經(jīng)過Maple計算后得出，當(dāng)λ3(T)≥0且λ4(T)<0時，G同構(gòu)于下列六十九個圖中的一個：

Ii(3≤i≤31)，I1⊙2v，I1·2v，I1⊕P3，

I1⊕P4，I1⊙v⊙P2，I1·v·P2，I1⊙2P2，I1+P3，
I1+P4，I2+v，I2⊕v，I2*v，I2+P2，

I2⊕P2，I2*P2，I2°2v，I2·2v，I3+v，I3⊕v，
I3·2v，I4+v，I4°2v，I5+v，I5⊕v，I7⊕v，

I8+v，I8⊕v，I9+v，I29v，I30+v，I30⊕v，
I31+v，I32⊕v，I32*v，I32⊕P2，I32*P2，

I32+v，I32+P2，I32v，I32P2.

定理5設(shè)G是一個k(k≥4)圈圖.若λ3(T)≥0且λ4(T)<0，則5≤n≤6+k．

證明由k≥4很容易看到，n≥5.假設(shè)n≥k+7.接下來，通過去點破除G中的圈.由于G是k圈圖，所以至多刪掉G中的k個點可以破圈.這樣，得到的G的誘導(dǎo)子圖就是一個至少含有七個點的樹T7.根據(jù)引理1及引理3，得出λ4(G)≥λ4(T7).這說明G的特征值至少有四個是非負(fù)的，這與G僅有三個非負(fù)特征值矛盾．

由上所述，可以確定5≤n≤6+k．

2 滿足λ3(G)≥0和λ4(G)<0的非連通圖G

參照文獻(xiàn)[4]，首先給出Gm的定義．

用NG(v)表示圖G中點v的鄰點集，再記NG[v]=NG(v)∪{v}.設(shè)G1和G2是兩個不交的完全圖，其點集分別為V(G1)={v1，v2，…，v「m/2?}和V(G2)={w1，w2，…，w?m/2」}.Gm(m≥2)是按照下面的要求在G1和G2之間添加一些邊之后得到的：

2) |NGm[vi]∩V(G2)|=i-1，這里的i=1，…，「m/2?；

3) 當(dāng)m為偶數(shù)時，有|NGm[wj]∩V(G1)|=j-1；當(dāng)m為奇數(shù)時，有|NGm[wj]∩V(G1)|=j，這里j=1，…，?m/2」．

下面的圖3給出了當(dāng)2≤m≤ 6時Gm的圖結(jié)構(gòu)．

圖3 Gm(2≤m≤6)Fig.3 Gm(2≤m≤6)

設(shè)Kn是n個點的完全圖.將Gm中的m個點v1，v2，…，vm分別用Kn1，Kn2，…，Knm去替換，并且如果vi和vj在Gm中是相鄰的且1≤i≠j≤m，那么就將Kni中的每個點和Knj中的每個點相連；否則，就不連.這樣得到的圖記為Gm[n1，n2，…，nm].

若圖X和圖Y是同構(gòu)的，那么記為X?Y；否則，記為XY．

引理4[5]設(shè)圖G是一個帶有n(n≥3)個點的連通圖，那么

1) 若λ2(G)>0且λ3(G)<0，則G?Gm[n1，n2，…，nm]，其中3≤m≤12，且Gm[n1，n2，…，nm]G3[1;1;n-2]；

2) 若λ2(G)=0且λ3(G)<0，則G?Kne．

所有患者術(shù)后72 h行顱腦增強(qiáng)MRI檢查腫瘤切除情況，根據(jù)Simpson分級標(biāo)準(zhǔn)，達(dá)到Ⅰ級 58例，Ⅱ級13例，Ⅲ級9例。術(shù)后送病理檢查均診斷為腦膜瘤，Ⅰ級良性腦膜瘤59例，Ⅱ級非典型性腦膜瘤21例。術(shù)后即時發(fā)現(xiàn)，8例多飲多尿者中6例癥狀緩解，2例無明顯改善；5例并發(fā)一過性尿崩；4例嗅覺減退；4例顱內(nèi)感染；1例腦脊液漏；1例出現(xiàn)高熱、血糖升高等嚴(yán)重下丘腦反應(yīng)而死亡；1例大量出血形成腦疝而死亡。隨訪2～7.5年，平均(5.4±1.4)年，56例視力不同程度的改善，21例無明顯變化，3例視力減退。11例復(fù)發(fā)，復(fù)發(fā)率為13.8%，再次行手術(shù)治療。

圖G的鄰接矩陣A(G)的特征多項式P(G，λ)=det(λI-A(G))也稱為圖G的特征多項式，這里的I表示n階單位矩陣．

引理5[5]設(shè)圖Gm(m≥ 2)的鄰接矩陣是A=(aij).其中n1，…，nm是正整數(shù)，令bii=ni-1(1≤i≤m)及bij=aijnj(1≤i≠j≤m)，設(shè)B=(bij)是m階矩陣.則P(Gm[n1，n2，…，nm]，λ)=(λ+1)n1+…+nm-mf(λ)，其中f(λ)=det(λI-B).并且-1是Gm[n1，n2，…，nm]的n1+…+nm-m重特征值．

引理6[5]設(shè)G是一個n≥ 2階連通圖.則λ1(G)>0且λ2(G)<0當(dāng)且僅當(dāng)G?Kn．

若G=B1∪B2∪…∪Bm，這里的m≥2,而B1，B2，…，Bm是m個沒有公共點且互不相連的連通圖，則稱G是非連通圖，B1，B2，…，Bm是G的m個連通分支．

定理6設(shè)G是一個n≥4階非連通圖.則有

1)λ3(G)>0且λ4(G)<0當(dāng)且僅當(dāng)G同構(gòu)于下面中的一個：

Gm[n1，n2，…，nm]∪Kc，Ka∪Kc∪Kn-a-c，

其中，3≤m≤12，Gm[n1，n2，…，nm]G3[1;1;a]且a，c≥2．

2)λ3(G)=0且λ4(G)<0當(dāng)且僅當(dāng)G同構(gòu)于下面中的一個：

Gm[n1，n2，…，nm]∪K1，Kqe∪Kn-q，

K1∪Kc∪Kn-1-c，K1∪K1∪Kn-2，

其中，3≤m≤12，Gm[n1，n2，…，nm]G3[1;1;n-3]且q≥ 3，c≥ 2．

證明假設(shè)G有m個連通分支B1，B2，…，Bm，即G=B1∪B2∪…∪Bm，其中m≥2.由Perron定理可知，λ1(Bi)≥0(1≤i≤m).因為λ4(G)<0，所以確定m≤3.由引理1及引理3容易看到，1)和2)都是成立的．

推論1如果G?G3[a;b;c]∪Kp，那么λ4(G)=-1．

證明若a=b=1，則G?G3[1;1;c]∪Kp.而G3[1;1;c]?Kc+2e.因此，λ4(G)=-1.若ab>1，則由引理5知，P(G3[a，b，c]，λ)=(λ+1)a+b+c-3f(λ)，其中

f(λ)=λ3-(a+b+c-3)λ2+(3+ab-2a-

2b-2c)λ+ac(b-1)+(a-1)(b+c-1).

設(shè)r1，r2，r3是f(λ)的三個根，那么依據(jù)根與系數(shù)的關(guān)系可得到

r1r2r3=-(ac(b-1)+(a-1)(b+c-1))<0

和

r1+r2+r3=a+b+c-3>0.

由此可看出，f(λ)有兩個正根和一個負(fù)根.注意到f(-1)=abc>0，所以當(dāng)λ→-∞時，f(λ)→-∞.可以看出，該負(fù)根在(-∞，-1)之間.又知-1是Kp的p-1重特征值，故可確定λ4(G)=-1．