余桂東，袁 慧，張子杰

(1.安慶師范大學(xué)數(shù)理學(xué)院，安徽 安慶 246133;2.合肥幼兒師范高等?？茖W(xué)校公共教學(xué)部，安徽 合肥 230013)

設(shè)G=(V(G),E(G))是n階簡(jiǎn)單無(wú)向圖，其頂點(diǎn)集為V=V(G)，邊集為E=E(G)。e(G)=|E(G)|表示圖G的邊數(shù)。NG(v)表示由頂點(diǎn)v∈V(G)的鄰點(diǎn)組成的集合，dG(v)=|NG(v)|表示頂點(diǎn)v的度。定義NG[v]=NG(v)∪{v}。若S是V(G)的非空子集，NG(S)表示與S中頂點(diǎn)相鄰的所有頂點(diǎn)的集合。用δ(G)(簡(jiǎn)記為δ)來(lái)表示G中頂點(diǎn)的最小度，G+H表示G和H不交并，G∨H表示在G+H中把G的每個(gè)頂點(diǎn)和H的每個(gè)頂點(diǎn)連接起來(lái)得到的圖。若S是V(G)的非空子集，則G[S]表示以S為頂點(diǎn)集、以G中兩端點(diǎn)均在S中的邊為邊集的圖。對(duì)于兩個(gè)點(diǎn)不交的V(G)的非空子集S和T，G[S,T]表示以S∪T為頂點(diǎn)集，以G中所有一個(gè)端點(diǎn)在S中，另一個(gè)端點(diǎn)在T中的邊為邊集的二部圖。對(duì)于非負(fù)整數(shù)n，若連續(xù)連接圖G中度和至少為n的不相鄰點(diǎn)對(duì)，直到?jīng)]有這樣的點(diǎn)對(duì)存在后，所得到的圖稱為圖G的n-閉包，記為cln(G)。圖G的n-閉包是唯一確定的，與所增加的邊的次序無(wú)關(guān)，并且在cln(G)中任意不相鄰點(diǎn)對(duì)u、v，有

dcln(G)(u)+dcln(G)(v)≤n-1。

設(shè)圖G的頂點(diǎn)集為{v1,v2,…,vn}。圖G的鄰接矩陣為A(G)=[aij]n×n，當(dāng)vi,vj相鄰時(shí)，aij=1，否則aij=0。圖G的度對(duì)角矩陣為D(G)=diag(d(v1),d(v2),…,d(vn))。圖G的無(wú)符號(hào)拉普拉斯矩陣為Q(G)=A(G)+D(G)。A(G)的最大特征值稱為圖G的譜半徑，記為ρ(G)。Q(G)的最大特征值稱為圖G的無(wú)符號(hào)拉普拉斯譜半徑，記為q(G)。圖G的一條途徑是指W=v0e1v1e2v2…ekvk，如果途徑內(nèi)部邊互不相同，且起點(diǎn)和終點(diǎn)相同，則稱為閉跡。如果一條閉跡的起點(diǎn)和內(nèi)部頂點(diǎn)互不相同，則稱為圈。如果一個(gè)圈包含圖的所有頂點(diǎn)，則稱為哈密爾頓圈。如果圖G包含一個(gè)哈密爾頓圈，則圖G是哈密爾頓圖。

長(zhǎng)期以來(lái)，判斷一個(gè)圖是否是哈密爾頓圖是NP-完全問(wèn)題。許多學(xué)者都在致力于尋找判斷一個(gè)圖是哈密爾頓圖的充分條件。文獻(xiàn)[1]2 171給出了當(dāng)δ(G)≥1時(shí)，圖G是哈密爾頓圖的譜半徑充分條件。文獻(xiàn)[2]改進(jìn)了文獻(xiàn)[1]2 171中最小度條件，研究了當(dāng)δ(G)≥2時(shí)，圖G是哈密爾頓圖的譜充分條件。文獻(xiàn)[3]2 258通過(guò)添加大的最小度條件，即δ(G)≥k≥1，探究圖G是哈密爾頓圖的譜充分條件。文獻(xiàn)[4]不僅改進(jìn)文獻(xiàn)[3]2 258中大的最小度條件，并且優(yōu)化了譜下界。文獻(xiàn)[5]27研究了δ(G)≥k≥1時(shí)，圖G是哈密爾頓圖的譜充分條件。受以上文獻(xiàn)的啟發(fā)，與文獻(xiàn)[5]30中證明方法相似，給出了帶有大的最小度圖是哈密爾頓圖的譜半徑和無(wú)符號(hào)拉普拉斯譜半徑充分條件。本文改進(jìn)了文獻(xiàn)[5]27中最小度條件，得到的邊數(shù)條件、譜半徑和無(wú)符號(hào)拉普拉斯譜半徑條件均優(yōu)化了文獻(xiàn)[5]28中的條件。

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

下面介紹需要用到的引理。

引理1[6]472圖G是哈密爾頓圖當(dāng)且僅當(dāng)cln(G)是哈密爾頓圖。

引理3[3]2262設(shè)2≤l≤k-1，F(xiàn)是階數(shù)為k的(k-l)正則圖，則Kl∨(F+Kn-l-k)是哈密爾頓圖。

引理5[5]29設(shè)圖G是n階圖有m條邊，且最小度為δ，則

2 主要結(jié)果

定理1設(shè)G是n階圖，其中n≥6k2+6k+2，δ(G)≥k≥2。若

則圖G是哈密爾頓圖，除非cln(G)=K1∨(Kk+Kn-k-1)或者cln(G)=Kk∨(Kn-2k+kK1)。

s(n-1)=n2-(2s+1)n+3s2+s。

因此

n2-(2k+1)n-k≤2e(H)≤n2-(2s+1)n+3s2+s，

即(2k-2s)n+3s2+s+k≥0。

斷言1s=k,d1=d2=…=dk=k。

矛盾。 故假設(shè)不成立， 因此s=k，δ(H)=k，d1=d2=…=dk=k。

斷言2H[{vk+1,…,vn}]=Kn-k。

證明斷言2 首先，證明dk+1≥n-3k2-3k-1。假設(shè)dk+1

矛盾。故假設(shè)不成立，因此有dk+1≥n-3k2-

3k-1。

接下來(lái)證明H[{vk+1,…,vn}]=Kn-k。因?yàn)閷?duì)于任意頂點(diǎn)對(duì)vi,vj，k+1≤i,j≤n,有

di+dj≥2(n-3k2-3k-1)=n。

由H=cln(G)的定義知，對(duì)于任意頂點(diǎn)對(duì)vi,vj均相鄰，k+1≤i,j≤n,即H[{vk+1,…,vn}]=Kn-k。

設(shè)X1={v1,…,vk}。因?yàn)閐1=d2=…=dk=k，|X1|=k，則X1的每個(gè)頂點(diǎn)至少與{vk+1,…,vn}中的一個(gè)頂點(diǎn)相鄰。設(shè)X2?NH(X1)∩{vk+1,vk+2,…,vn}。對(duì)于任意x∈V(H)，令NX2(x)=

X2∩NH(x)，|X2|=l，其中1≤l≤k。

斷言3H[X1,X2]=Kk,l。

證明斷言3 假設(shè)H[X1,X2]≠Kk,l，則存在不同頂點(diǎn)u,v∈X1，w∈X2，使得w∈NX2(u)NX2(v)。

因?yàn)閐H(w)≥n-k，則

dH(v)+dH(w)≥k+n-k=n。

由閉包定義知w∈NX2(v)，這與w∈NX2(u)NX2(v)矛盾。假設(shè)不成立，因此H[X1,X2]=Kk,l。

結(jié)合以上3個(gè)斷言，若l=1，則H=K1∨(Kk+Kn-k-1)；若l=k，則H=Kk∨(Kn-2k+kK1)； 若2≤l≤

k-1的情況，應(yīng)用引理3知H是哈密爾頓圖，與假設(shè)矛盾，證明完畢。

實(shí)際上，文獻(xiàn)[5]30也給出了與定理1相似的定理。

定理2[5]30設(shè)G是n階圖，其中n≥6k2+4k+2，δ(G)≥k≥1。若

則圖G是哈密爾頓圖，除非cln(G)=K1∨(Kk+

Kn-k-1)或者cln(G)=Kk∨(Kn-2k+kK1)。

注：在k≥2的情況下，

而由于哈密爾頓圖G的必要條件是δ(G)≥

k≥2，故定理1優(yōu)化了定理2。

定理3設(shè)圖G是n階圖， 其中n≥6k2+6k+2，δ(G)≥k≥2。若

則圖G是哈密爾頓圖，除非cln(G)=K1∨(Kk+

Kn-k-1)或者cln(G)=Kk∨(Kn-2k+kK1)。

證明根據(jù)引理4和引理6，得到

假設(shè)G不是哈密爾頓圖，則根據(jù)定理1知，cln(G)=K1∨(Kk+Kn-k-1)或者cln(G)=Kk∨(Kn-2k+kK1)，證明完畢。

定理4[5]27設(shè)圖G是n階圖，其中n≥6k2+4k+2，δ(G)≥k≥1。若

則圖G是哈密爾頓圖，除非cln(G)=K1∨(Kk+

Kn-k-1)或者cln(G)=Kk∨(Kn-2k+kK1)。

注：在k≥2的情況下，

因此定理3優(yōu)化了定理4。

定理5設(shè)G是n階圖， 其中n≥6k2+6k+2，δ(G)≥k≥2。若

則圖G是哈密爾頓圖，除非cln(G)=K1∨(Kk+

Kn-k-1)或者cln(G)=Kk∨(Kn-2k+kK1)。

證明 根據(jù)引理5，得到

假設(shè)G不是哈密爾頓圖，則根據(jù)定理1知，cln(G)=K1∨(Kk+Kn-k-1)或者cln(G)=Kk∨(Kn-2k+kK1)，證明完畢。

定理6[5]28設(shè)圖G是n階圖，其中n≥6k2+4k+2，δ(G)≥k≥1。若

則圖G是哈密爾頓圖，除非cln(G)=K1∨(Kk+

Kn-k-1)或者cln(G)=Kk∨(Kn-2k+kK1)。

注：在k≥2的情況下，

因此定理5優(yōu)化了定理6。

3 結(jié)論

本文利用圖的閉包以及度序列，首先得到帶有大的最小度圖是哈密爾頓圖的邊數(shù)條件，然后根據(jù)邊數(shù)與譜之間的關(guān)系，給出帶有大的最小度圖是哈密爾頓圖的譜、無(wú)符號(hào)拉普拉斯譜充分條件。