圖的某些特殊性質(zhì)的譜條件

王 磊，蔡改香，劉 莉

（安慶師范大學(xué)數(shù)理學(xué)院，安徽安慶246133）

設(shè)G=(V(G),E(G))是n階簡(jiǎn)單圖，其頂點(diǎn)集為V=V(G)，邊集為E=E(G)。記Gc=(V,Ec)為圖G=(V,E)的補(bǔ)圖，其中Ec={xy:x,y∈V,x≠y,xy?E}。頂點(diǎn)v的度d G(v)指G中與v關(guān)聯(lián)的邊數(shù)，G的最大度與最小度分別記為Δ(G)和δ(G)。圖G的鄰接矩陣A(G)=[aij]n×n，當(dāng)vi、vj相鄰時(shí)，aij=1，否則aij=0，i,j=1,2,3,…,n。A(G)的最大特征值μ(G)稱為G的譜半徑。設(shè)S?V，圖G[S]表示以S為頂點(diǎn)集，以G中兩端點(diǎn)均在S中的邊為邊集的圖，若圖G[S]中無(wú)邊，則稱S為G的獨(dú)立集。G中含點(diǎn)數(shù)最多的獨(dú)立集所含點(diǎn)數(shù)稱為G的獨(dú)立數(shù)，記為α(G)。如果G中所有頂點(diǎn)的度都相等，則稱圖G為正則圖。如果Δ(G)=δ(G)=n-1，則稱G為完全圖，記作Kn。如果圖的頂點(diǎn)集V可以被劃分為互不相交的子集X和Y，使得V=X?Y，且任意邊uv滿足u∈X，v∈Y或u∈Y，v∈X，則稱G為二部圖，記作GBPT=(X,Y;E)。若對(duì)任意u∈X，d GBPT(u)相同，且任意v∈Y，d GBPT(v)也相同，則稱GBPT為二部半正則圖。設(shè)G1=(V1,E1)，G2=(V2,E2)是2個(gè)頂點(diǎn)不相交的簡(jiǎn)單圖，它們的并圖為G1?G2=(V1?V2,E1?E2)，聯(lián)圖為G1∨G2=((G1)c?(G2)c)c。對(duì)于非負(fù)整數(shù)k，若連續(xù)連接圖G中的度和不小于k的不相鄰點(diǎn)對(duì)，直到?jīng)]有這樣的點(diǎn)對(duì)存在，所得到的圖稱為圖G的k-閉包，記作clk(G)。圖G的k-閉包是唯一確定的，與所增加的邊的次序無(wú)關(guān)，并且在clk(G)中任意不相鄰點(diǎn)對(duì)u，v，有d clk(G)(u)+d clk(G)(v)≤k-1。其余相關(guān)概念和術(shù)語(yǔ)可參考文獻(xiàn)[1]。

如果一條閉路徑的起點(diǎn)和內(nèi)部頂點(diǎn)互不相同，則稱它為圈，一條包含圖G中所有頂點(diǎn)的路稱為哈密爾頓路，一個(gè)包含圖G中所有頂點(diǎn)的圈稱為哈密爾頓圈。若圖G包含一個(gè)哈密爾頓圈，則稱圖G是哈密爾頓圖。若圖G中任意兩個(gè)頂點(diǎn)都被一條哈密爾頓路連接，則稱G是哈密爾頓-連通圖。設(shè)X是圖G的任意頂點(diǎn)集且X?V(G)，這里X中頂點(diǎn)數(shù)為s，如果圖G-X是哈密爾頓-連通圖，則稱圖G是s-哈密爾頓-連通圖。設(shè)S表示圖G中s個(gè)頂點(diǎn)的集合，如果對(duì)任意正整數(shù)i(3≤i≤s)，在圖G中均存在圈C，使得|V(C)?S|=i，則稱圖G為S-泛圈圖。馮立華等人在文獻(xiàn)[2]中提出了給定大的最小度的圖是s-哈密爾頓圖或s-路-覆蓋圖的譜充分條件。余桂東等人在文獻(xiàn)[3]中根據(jù)補(bǔ)圖的譜半徑提出了給定大的最小度的圖是s-連通圖、s-路-覆蓋圖、s-邊-連通圖的充分條件。受文獻(xiàn)[3]的啟發(fā)，本文主要根據(jù)補(bǔ)圖的譜半徑提出給定大的最小度的圖是s-哈密爾頓-連通圖、S-泛圈圖或α(G)≤s的充分條件。

1 預(yù)備知識(shí)

下面介紹需要用到的4類特殊圖類及引理。

NP1是滿足下列條件的n階圖的集合：G1∨G2，其中，G1是n-k+r階的(n-k-1)-正則圖，G2是Kk-r的生成子圖。

NP2是滿足下列條件的n階圖的集合：Gc1∨G2，其中，G1=(X,Y)是階為n-s-2+r的二部半正則圖，并且對(duì)任意頂點(diǎn)u∈X，v∈Y分別有d G1(u)=k-s-1，d G1(v)=n-k-1，G2是Ks+2-r的生成子圖。

NP3是滿足下列條件的n階圖的集合：Gc1∨G2，其中，G1=(X,Y)是階為n-s+2+r的二部半正則圖，并且對(duì)任意頂點(diǎn)u∈X，v∈Y分別有d G1(u)=k-s+3，d G1(v)=n-k-1，G2是Ks-2-r的生成子圖。

NP4是滿足下列條件的n階圖的集合：G c1∨G2，其中，G1=(X,Y)是階為2s+r的二部半正則圖，并且對(duì)任意頂點(diǎn)u∈X，v∈Y分別有d G1(u)=k+2s-n+1，d G1(v)=n-k-1，G2是Kn-2s-r的生成子圖。

引理1[4-5]（1）設(shè)n，s是正整數(shù)且s≤n-4，那么“圖G是s-哈密爾頓-連通圖”是(n+s+1)-穩(wěn)定的。

（2）設(shè)n，s是正整數(shù)且3≤s≤n，那么“圖G是S-泛圈圖”是(n+s-3)-穩(wěn)定的。

（3）設(shè)n，s是正整數(shù)且s≤n，那么“α(G)≤s”是(2n-2s-1)-穩(wěn)定的。

引理2[4]設(shè)P是n階圖G的一個(gè)性質(zhì)，如果P是k-穩(wěn)定的且clk(G)有性質(zhì)P，那么圖G本身就有性質(zhì)P。

引理3[6]設(shè)G是一個(gè)邊集非空的圖，則如果G是連通圖，當(dāng)且僅當(dāng)G是正則圖或二部半正則圖時(shí)等號(hào)成立。

2 主要結(jié)果

定理1設(shè)G是n階簡(jiǎn)單圖且最小度δ(G)≥k≥1，k-s+2≥0，n≥2k+1。如果μ(Gc)≤則G是s-哈密爾頓-連通圖，除非G∈NP1或G∈NP2。

證明假設(shè)圖G不是s-哈密爾頓-連通圖，構(gòu)造閉包H:=cln+s+1(G)。根據(jù)引理1（1）及引理2，圖H不是s-哈密爾頓-連通圖，因此H中任意兩個(gè)不相鄰頂點(diǎn)u，v的度和至多為n+s，對(duì)任意邊uv∈E(H c)，有

因?yàn)閐 H(u)≥d G(u)≥k且d H(v)≥d G(v)≥k，所以有d Hc(u)≤n-k-1，d Hc(v)≤n-k-1。結(jié)合式（1），可得dHc(u)≥n-s-2-dHc(v)≥k-s-1，dHc(v)≥n-s-2-dHc(u)≥k-s-1。

設(shè)f(x)=x(n-s-2-x)，其中k-s-1≤x≤n-k-1，這里f(x)是關(guān)于x的凹函數(shù)，于是f(x)≥f(k-s-1)=f(n-k-1)，自然有f(x)≥(k-s-1)(n-k-1)，當(dāng)且僅當(dāng)x=k-s-1或x=n-k-1時(shí)等式成立。因此，

3 結(jié)論

本文針對(duì)圖的不同特殊性質(zhì)，首先找到了相應(yīng)的穩(wěn)定性，然后進(jìn)行了閉包運(yùn)算，將復(fù)雜的原圖是否具有某性質(zhì)問(wèn)題轉(zhuǎn)化為閉包的補(bǔ)圖來(lái)考慮，最后結(jié)合譜半徑的性質(zhì)及原圖與閉包補(bǔ)圖之間的微妙關(guān)系，巧妙地利用了補(bǔ)圖的譜半徑判定原圖是否具有該性質(zhì)。這種利用補(bǔ)圖譜半徑判定原圖的某些性質(zhì)是否存在的方法，為我們提供了一種新穎的思維方式。