無符號拉普拉斯譜半徑與圖的哈密爾頓性

何 煥，王禮想，葉淼林

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

圖G的鄰接矩陣為A(G)=(aij)n×n，如果vivj∈E，則aij=1，否則aij=0，i,j=1,2,3,…,n。圖G的度對角矩陣為D(G)=diag(d(v1),d(v2),d(v3),…,d(vn))，因此圖G的無符號拉普拉斯矩陣為Q(G)=D(G)+A(G)。顯然A(G)，Q(G)是實對稱矩陣，所以其特征值均為實數(shù)且可以排序。A(G)的最大特征值λ(G)稱為G的譜半徑。Q(G)的最大特征值q(G)稱為圖G的無符號拉普拉斯譜半徑。如果圖G中任意兩個點之間均能找到一條哈密爾頓路，則稱G是哈密爾頓-連通圖。如果圖G中從任意點出發(fā)均能找到一條哈密爾頓路，則稱G是從任意點出發(fā)可跡的。若連續(xù)連接圖G中度和不小于k的不相鄰點對，直到?jīng)]有這樣的點對存在，所得到的圖稱為G的k-閉包，記作Ck(G)。圖G的k-閉包是唯一確定的，與所增加邊的次序無關(guān)，并且在Ck(G)中任意不相鄰點對u,v，均有

圖的哈密爾頓問題一直是圖論的熱點問題，也是NP-完全問題。圖的譜不但能夠很好的反映圖的結(jié)構(gòu)性質(zhì)且便于計算，所以圖的譜理論被廣泛用來解決此類問題。利用圖的譜半徑和無符號拉普拉斯譜半徑來刻畫圖的哈密爾頓性取得了很多成果，如李斌龍等[2]給出了簡單圖和平衡二部圖是可跡的和哈密爾頓的（無符號拉普拉斯）譜充分條件。余桂東等[3-4]研究了具有較大最小度的平衡二部圖是可跡的和哈密爾頓的譜充分條件，以及利用譜半徑和無符號拉普拉斯譜半徑去刻畫圖的泛圈性的充分條件；周倩楠等[5]研究了具有較大最小度的圖是哈密爾頓-連通的無符號拉普拉斯譜充分條件。徐奕等[6]分別借助圖的大小、譜半徑和無符號拉普拉斯譜半徑給出了圖是哈密爾頓-連通的一些充分條件。此外，周波[7]利用補圖的無符號拉普拉斯譜半徑給出了圖存在哈密爾頓路和哈密爾頓圈的充分條件。而利用補圖的無符號拉普拉斯譜半徑去刻畫具有較大最小度的圖是哈密爾頓-連通問題至今還缺乏研究。受此啟發(fā)，本文利用補圖的無符號拉普拉斯譜半徑給出了具有較大最小度的圖分別是哈密爾頓的、哈密爾頓-連通的以及從任意點出發(fā)可跡的的充分條件。

1 預(yù)備知識

引理1[2]設(shè)G是一個邊集非空的圖，則λ(G)≥若G是連通圖，當(dāng)且僅當(dāng)G是正則圖或二部半正則圖時等號成立。對引理1進行擴展，使其適用范圍從鄰接矩陣到無符號拉普拉斯矩陣。

引理2設(shè)G是n階連通圖，則q(G)≥2λ(G)，當(dāng)且僅當(dāng)G是正則圖時等號成立。

下面給出圖的哈密爾頓性與圖閉包的哈密爾頓性間關(guān)系，以及特殊條件下正則圖的哈密爾頓性。

引理4[2]設(shè)G是n階圖，G是哈密爾頓圖當(dāng)且僅當(dāng)Cn(G)是哈密爾頓圖。

引理5[1]當(dāng)k≥2時，任意2k+1階k-正則圖都是哈密爾頓圖。

引理6[8]設(shè)G是n階圖，G是哈密爾頓-連通圖當(dāng)且僅當(dāng)Cn+1(G)是哈密爾頓-連通圖。

引理7[9]（1）設(shè)t≥3和圖G是2t階不同構(gòu)于Kt,t的t-正則圖，則G是哈密爾頓-連通圖。

（2）設(shè)t≥4且為偶數(shù)，G是2t+1階t-正則圖，則G是哈密爾頓-連通圖。

引理8[1]設(shè)G是n階圖，G從任意一點出發(fā)都是可跡的當(dāng)且僅當(dāng)G∨K1是哈密爾頓-連通圖。

2 主要結(jié)果

周波[7]利用補圖的無符號拉普拉斯譜半徑給出了簡單圖存在哈密爾頓路和哈密爾頓圈的充分條件。由于圖的最小度與圖的疏密性有關(guān)，因此本文在文獻[7]的基礎(chǔ)上添加了較大最小度這個條件，并運用新的方法得出了新結(jié)論，該結(jié)論的譜條件范圍更精確且適用范圍更優(yōu)于文獻[7]中的結(jié)論，并且在此基礎(chǔ)上討論了圖的哈密爾頓-連通性和從任意點出發(fā)可跡的性質(zhì)。

由引理3和Perron-Frobenius定理知

3 結(jié)論

本文系統(tǒng)研究了圖的哈密爾頓性，主要是利用圖的閉包思想將原圖不容易解決的問題轉(zhuǎn)化為補圖的閉包來解決，再結(jié)合計算出的補圖的譜半徑的上界，得出原圖的哈密爾頓性。本文的研究方法為挖掘哈密爾頓圖的譜充分條件提供了一個新思路。