圖的哈密爾頓性的Aα-譜條件

何 煥，葉淼林

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

本文考慮的所有圖都是簡(jiǎn)單無(wú)向圖。設(shè)G=(V,E)為n階圖，其頂點(diǎn)集V=V(G)={v1,v2,v3,…,vn}，邊集E=E(G)={e1,e2,e3,…,em}。圖G的鄰接矩陣記為A(G)，圖G的度對(duì)角矩陣記為D(G)。圖G的頂點(diǎn)v的度是指G中與v關(guān)聯(lián)的邊數(shù)目，用dG(v)表示，記δ為G的頂點(diǎn)的最小度。記Kn、K1,n-1、Km,n-m分別是n階完全圖、星圖、完全二部圖。文獻(xiàn)[1]最先給出了Aα-譜的概念，對(duì)于任意的實(shí)數(shù)α∈[ 0,1 ]，稱(chēng)Aα(G)=αD(G)+( 1-α)A(G)為圖G的Aα-矩陣。設(shè)Aα(G)的n個(gè)特征值從大到小排列為λ1(Aα(G))≥λ2(Aα(G))≥λ3(Aα(G))≥…≥λn(Aα(G))，最大特征值λ1(Aα(G))稱(chēng)為G的Aα-譜半徑，記為λ(Aα(G))。設(shè)G1=(V1,E1)與G2=(V2,E2)是兩個(gè)頂點(diǎn)不交的圖，它們的并圖為G1?G2=(V1?V2,E1?E2)，又記為G1+G2；它們的聯(lián)圖記為G1∨G2，即在G1+G2中添加由G1中每個(gè)頂點(diǎn)到G2中每個(gè)頂點(diǎn)的邊所構(gòu)成的圖。一條包含圖G中所有頂點(diǎn)的路稱(chēng)為哈密爾頓路，如果圖G中任意兩個(gè)頂點(diǎn)都被一條哈密爾頓路相連，則稱(chēng)G是哈密爾頓-連通的。一個(gè)包含圖G中所有頂點(diǎn)的圈被稱(chēng)為哈密爾頓圈。如果圖G包含一個(gè)哈密爾頓圈，則稱(chēng)G是哈密爾頓圖。如果圖G含有哈密爾頓路，則稱(chēng)G是可跡圖。文中沒(méi)有提到的概念和術(shù)語(yǔ)可參考文獻(xiàn)[2]。

圖的哈密爾頓問(wèn)題是一個(gè)經(jīng)典且困難的問(wèn)題，近幾年來(lái)關(guān)于這類(lèi)問(wèn)題的研究較多。Fiedler等根據(jù)圖的鄰接矩陣或其補(bǔ)圖的譜半徑給出了圖含有哈密爾頓路或哈密爾頓圈的充分條件[3]。周波利用圖的補(bǔ)圖的無(wú)符號(hào)拉普拉斯矩陣的譜半徑，給出了圖包含哈密爾頓路和哈密爾頓圈的一些條件[4]。Butler等建立了一個(gè)圖是哈密爾頓的充分條件，即拉普拉斯矩陣的非平凡特征值充分接近于圖的平均度[5]。余桂東等根據(jù)圖的鄰接矩陣或無(wú)符號(hào)拉普拉斯矩陣或其補(bǔ)圖的譜半徑，給出了圖是哈密爾頓-連通的一些譜充分條件，同時(shí)利用無(wú)符號(hào)拉普拉斯譜半徑，給出了圖含有哈密爾頓路或哈密爾頓圈的條件[6]。受文獻(xiàn)[6]啟發(fā)，本文給出了具有最小度數(shù)條件的連通圖是哈密爾頓-連通的、哈密爾頓的和可跡的譜充分條件。

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

下面介紹需要用到的相關(guān)概念和引理。

給定一個(gè)含n個(gè)頂點(diǎn)的圖G，如果對(duì)應(yīng)于Aα-特征向量X={X1,X2,X3,…,Xn}T的特征值是λ，則根據(jù)Aα-特征值的定義，當(dāng)且僅當(dāng)X≠0，且對(duì)于每個(gè)u,v，顯然矩陣的特征等式為

2 主要結(jié)果

受無(wú)符號(hào)拉普拉斯譜半徑與哈密爾頓性的啟發(fā)，本文想要尋找Aα-譜半徑與哈密爾頓-連通性之間的關(guān)系，又因?yàn)槔脠D的邊數(shù)去刻畫(huà)譜充分條件比較簡(jiǎn)單，所以借助上面的引理?xiàng)l件得到了下面的結(jié)論。

假設(shè)G不是哈密爾頓-連通的，則由引理2可得G∈NP1。

如果G=K4∨4K1，則設(shè)X={X1,X2,X3,…,X8}T是Aα(G)的特征值λ(Aα(G))所對(duì)應(yīng)的特征向量。由圖G的Aα-特征等式（1）可知，所有度為7的頂點(diǎn)在X中對(duì)應(yīng)的值相同，記為X1；所有度為4的頂點(diǎn)在X中對(duì)應(yīng)的值相同，記為X2。仍由圖G的Aα-特征等式（1），令λ=λ(Aα(G))，有

將式（2）轉(zhuǎn)化成矩陣等式(B-λI)X′=0，這里X′=(X1,X2)T，

如果G=K4∨(K1,4+K1)，則設(shè)X={X1,X2,X3,…,X10}T是Aα(G)的特征值λ(Aα(G))所對(duì)應(yīng)的特征向量。由圖G的Aα-特征等式（1）可知，所有度為9的頂點(diǎn)在X中對(duì)應(yīng)的值相同，記為X1；所有度為8的頂點(diǎn)在X中對(duì)應(yīng)的值相同，記為X2；所有度為5的頂點(diǎn)在X中對(duì)應(yīng)的值相同，記為X3；所有度為4的頂點(diǎn)在X中對(duì)應(yīng)的值相同，記為X4。仍由圖G的Aα-特征等式（1），λ=λ(Aα(G))，有

將式（3）轉(zhuǎn)化成矩陣等式(B-λI)X′=0，這里X′=(X1,X2,X3,X4)T，

如果G=K3∨(K1,3+K1)，則設(shè)X=(X1,X2,X3,…,X8)T是Aα(G)的特征值λ(Aα(G))所對(duì)應(yīng)的特征向量。由圖G的Aα-特征等式（1）可知，所有度為7的頂點(diǎn)在X中對(duì)應(yīng)的值相同，記為X1；所有度為6的頂點(diǎn)在X中對(duì)應(yīng)的值相同，記為X2；所有度為4的頂點(diǎn)在X中對(duì)應(yīng)的值相同，記為X3；所有度為3的頂點(diǎn)在X中對(duì)應(yīng)的值相同，記為X4。仍由圖G的Aα-特征等式（1），令λ=λ(Aα(G))，有

3 結(jié)論

目前，利用鄰接譜半徑、無(wú)符號(hào)拉普拉斯譜半徑、拉普拉斯譜半徑去刻畫(huà)圖的哈密爾頓-連通性、哈密爾頓性和可跡性是十分常見(jiàn)的，比如文獻(xiàn)[6]就是利用無(wú)符號(hào)拉普拉斯譜半徑去刻畫(huà)圖的哈密爾頓性。但是，利用Aα-譜半徑去刻畫(huà)圖的哈密爾頓-連通性、哈密爾頓性和可跡性的文獻(xiàn)較少。本文借助文獻(xiàn)[6]的思想，通過(guò)刻畫(huà)Aα-譜半徑，給出了具有最小度數(shù)條件的連通圖是哈密爾頓-連通的、哈密爾頓的和可跡的譜充分條件。今后，希望可以找到一種較為合適的方法來(lái)利用Aα-譜半徑去判斷圖的這些性質(zhì)，從而優(yōu)化本文中的一些結(jié)論。