【摘 要】 設(shè)[G]是一個(gè)簡(jiǎn)單圖，[G]的鄰接矩陣是表示[G]頂點(diǎn)之間相鄰關(guān)系的矩陣，它的最大特征值被定義為圖的譜半徑。一個(gè)包含圖[G]中所有頂點(diǎn)的圈稱為哈密爾頓圈，如果圖[G]包含一個(gè)哈密爾頓圈，則稱圖[G]是哈密爾頓圖。設(shè)[G]具有最小度條件，主要利用[G]的譜半徑給出[G]是哈密爾頓圖的充分條件。

【關(guān)鍵詞】 連通圖；哈密爾頓圖；譜半徑；最小度

Spectral Radius Condition of Hamiltonian Graph

Fang Yi1， Xie Xinyu2， Qian Wangsheng1

（1.Tongling Polytechnic， Tongling 244061， China;

2.Anqing Normal University， Anqing 246133， China）

【Abstract】 Let [G] be a simple graph. The adjacency matrix of [G] is the one which represents adjacent relation between vertices of [G]， the largest eigenvalue of the adjacency matrix of which is called the spectral radius of [G]. A Hamiltonian cycle of [G] is a cycle which contains all vertices of [G]. The graph [G] is called Hamiltonian graph if it contains a Hamiltonian cycle. Let [G] have minimum degree condition， and this paper mainly studies some conditions for [G] to be a Hamiltonian graph in terms of the spectral radius.

【Key words】 graph; Hamiltonian graph; spectral radius; minimum degree

〔中圖分類(lèi)號(hào)〕 O157.5 〔文獻(xiàn)標(biāo)識(shí)碼〕 A 〔文章編號(hào)〕 1674 - 3229（2024）03 - 0030 - 03

0 引言

本文研究簡(jiǎn)單無(wú)向圖。首先介紹圖的符號(hào)表示，設(shè)[G=VG，EG]是一個(gè)[n]階簡(jiǎn)單連通圖，其頂點(diǎn)集[VG=v1，v2，…，vn]，定義[n=VG]為[G]的階數(shù)，頂點(diǎn)[vi∈VG]的鄰域定義為[NGvi]，表示與[vi]相連的點(diǎn)的集合。頂點(diǎn)[vi]的度[dGvi=NGvi]（簡(jiǎn)寫(xiě)為[di]），不失一般性，設(shè)[d1≤d2≤…≤dn]，記[d1，d2，…，dn]為[G]的度序列，[G]的最小度記為[δG]。定義[m=EG]為[G]的邊數(shù)。設(shè)[G1]和[G2]是兩個(gè)頂點(diǎn)不相交的簡(jiǎn)單圖，其并圖[G1?G2=VG1?VG2，EG1?EG2]，它們的聯(lián)圖[G1∨G2]是由[G1?G2]添加[G1]中每個(gè)頂點(diǎn)到[G2]中每個(gè)頂點(diǎn)的邊構(gòu)成的圖。設(shè)點(diǎn)集[S?VG]，則[GS]表示由點(diǎn)集[S]產(chǎn)生的子圖。記[Kn]為[n]階完全圖，[On=Kn]為[n]階空?qǐng)D（不含邊），[Kn，m=On∨Om]為完全二部圖。

圖[G]的譜半徑記為[μG]，定義為圖[G]的鄰接矩陣的最大特征值。圖[G]的鄰接矩陣定義為[AG=aijn×n]，其中當(dāng)[vi]，[vj]相鄰時(shí)，[aij=1]，否則[aij=0] 。

哈密爾頓圖的譜半徑條件是圖論中經(jīng)典且很困難的問(wèn)題。陸枚等［1］對(duì)圖的邊數(shù)條件進(jìn)行優(yōu)化，從而給出利用譜半徑判斷一個(gè)圖是哈密爾頓圖的充分條件，余桂東［2］利用補(bǔ)圖的譜半徑給出原圖含有哈密爾頓路、哈密爾頓圈以及原圖是哈密爾頓-連通圖的一些譜條件。如果一個(gè)圖是哈密爾頓圖，那么它的最小度大于等于2，因此可以將圖的最小度與圖的哈密爾頓性緊密聯(lián)系在一起，這又是后面學(xué)者研究的重點(diǎn)內(nèi)容。Nikiforov［3］研究了帶有最小度的圖的哈密爾頓性的譜半徑條件，余桂東等［4］進(jìn)一步研究了帶有最小度的圖（平衡二部圖）的哈密爾頓性的譜半徑條件，隨后江貴生等［5］、劉珍珍等［6］、余桂東等［7］進(jìn)行了進(jìn)一步研究。除了利用譜半徑判斷圖的哈密爾頓性以外，方怡等［8］、劉莉等［9］利用無(wú)符號(hào)拉普拉斯譜半徑判斷圖的一些性質(zhì)。本文將對(duì)哈密爾頓圖的譜半徑條件進(jìn)行進(jìn)一步研究。

1 相關(guān)引理

引理1.1［10］ 設(shè)圖[G]是一個(gè)[n]階圖，有[m]條邊，則[μG≤2m-n+1]，當(dāng)且僅當(dāng)[G=Kn]或[G=K1，n-1]時(shí)等式成立。

引理1.2［11］ 設(shè)[G]是一個(gè)[n]階圖，滿足度序列[d1≤]

[d2≤…≤dn]。假設(shè)不存在整數(shù)[s<n2]使得[ds≤s]，[dn-s≤n-s-1]同時(shí)成立，則圖[G]是哈密爾頓圖。

引理1.3［12］ 設(shè)[G]是一個(gè)[n]階連通圖，其中[n≥6]，有[m]條邊，且最小度[δG≥3]，如果

[eG≥n-3 2+6]，

則圖[G]是哈密爾頓連通圖除非

[G∈NP1=K3∨Kn-5+2K1，K6∨6K1，K4∨K2+3K1，5K1∨K5， K4∨K1，4 + K1， K4∨K1，3 + K2， K3 ∨ K2，5，K4∨4K1， K3∨K1 + K1，3， K3∨K1，2 + K2， K2∨K2，4]

引理1.4［3］ 設(shè)[k≥1]，[n≥k32+k+4]，[G]是一個(gè)[n]階圖，最小度滿足[δG≥k]，則

（1）如果[G]是[Mkn]的一個(gè)子圖，則[μG<n-k-1]，

除非[G=Mkn]；

（2）如果[G]是[Lkn]的一個(gè)子圖，則[μG<n-k-1]，

除非[G=Lkn]。

注：[Lkn：=K1∨Kn-k-1+Kk，][Mkn：=Kk∨（Kn-2k+]

[kK1）]，其中[k≥1]且[n≥2k+1]。

2 主要結(jié)論

定理 2.1 設(shè)圖[G]是一個(gè)[n]階圖，[n>21]，[δG≥3]。如果[eG≥n-3 2+2]，

[G?L3n]或[G?M3n]，則圖[G]是哈密爾頓圖。

證明：假設(shè)圖[G]滿足上述條件但是圖[G]不是哈密爾頓圖。設(shè)[d1，d2，…，dn]是圖[G]的度序列，根據(jù)引理1.2，存在一個(gè)整數(shù)[s<n2]，使得[ds≤s]且[dn-s≤n-s-1]，記[m]是圖[G]的邊數(shù)，顯然

[m=12i=1sdvi+i=s+1n-sdvi+i=n-s+1ndvi ≤12n2-2sn+3s2+s-n =n-3 2+2+3s2-2sn+s+6n-162]

記[fs=3s2-2sn+s+6n-16。]因?yàn)閇eG≥n-3 2]

[+2]，所以[fs≥0]，且[3≤s≤n-12]。

當(dāng)[4≤s≤n-12]，其中[n>21]，通過(guò)直接計(jì)算，得到[f4=36-2n<0]，[fn-12=-n2+24n-634≤0]，產(chǎn)生矛盾。

當(dāng)[s=3]，通過(guò)直接計(jì)算，得到[f3=14>0]。

因此，只要討論當(dāng)[s=3]時(shí)的情形。由于[3≤δG≤d3≤3]，得到

[d1=d2=d3=3，] [d4≤d5≤…≤dn-3≤n-4，] [dn-2≤][dn-1][≤dn≤n-1] （1）

因此

[m=12i=13dvi+i=4n-3dvi+i=n-2ndvi ≤1232+n-6n-4+3n-1 =12n2-7n+30 =n-3 2+9]

所以有[n-3 2+2≤eG≤n-3 2+9]。

如果[eG=n-3 2+9，] 則[i=1ndvi=2eG=n2-7n+]

[30]，從這里可以計(jì)算出（1）中的不等式必須是等式，所以圖[G]的度序列[（3，3，3，n-4，n-4，…，n-4，n-1，]

[n-1，n-1）]，將3個(gè)度為[3]的點(diǎn)記為[A]，[n-6]個(gè)度為[n-4]的點(diǎn)記為[B]，3個(gè)度為[n-1]的點(diǎn)記為[C]。這表明[G?M3n]，與定理?xiàng)l件矛盾。

如果[eG=n-3 2+2+7-t]，其中[1≤t≤7]，則得到

[eG=eM3n-t]，[eG=eL3n-t-3]

注意到任意[t]個(gè)[3]度點(diǎn)最多關(guān)聯(lián)[3t]條邊，任意[n-t]個(gè)點(diǎn)最多連接[n-t 2]條邊，即當(dāng)[G]有[t]個(gè)[3]度頂點(diǎn)時(shí)，至多構(gòu)成[n-t 2+3t]條邊。由于[eG≥n-3 2+2]，故[t≤3]，由度序列（1），得到圖[G]恰有3個(gè)[3]度點(diǎn)。在這種情況下，只能減少[VB?C]中點(diǎn)的度數(shù)，即在[GB?C]中去邊。接下來(lái)考慮下面2種情況。

第一種情況：[VA]中的點(diǎn)只與[VB?C]中一個(gè)點(diǎn)相連。在這種情況下，[G?L3N]，與定理?xiàng)l件矛盾。

第二種情況：[VA]中的點(diǎn)與[VB?C]中至少2個(gè)點(diǎn)相連。在這種情況下，需要考慮下面4種情況。

（1）[GA]中有3條邊。在這種情況下，[GA=K3]是一個(gè)完全圖，證明[G]是哈密爾頓圖只需要證明[GB?C]是哈密爾頓連通圖。由于

[eGB?C=n-3 2+9-6-t ≥n-3 2+9-6-7 >n-3-3 2+6]

根據(jù)引理1.3，[GB?C]是哈密爾頓連通圖，故[G]是哈密爾頓圖，矛盾。

（2）[GA]中有2條邊。 在這種情況下，[GA=P3]是一條路，[VB?C]中至少有2個(gè)點(diǎn)與[VA]中點(diǎn)相連。因此證明[G]是哈密爾頓圖只需要證明[GB?C]是哈密爾頓連通圖。由于

[eGB?C=n-3 2+9-7-t ≥n-3 2+9-7-7 >n-3-3 2+6]

根據(jù)引理1.3，[GB?C]是哈密爾頓連通圖，故[G]是哈密爾頓圖，矛盾。

（3）[GA]中有1條邊。 在這種情況下，[GA]中有一個(gè)獨(dú)立的點(diǎn)[v]，證明[G]是哈密爾頓圖，需要證明[GB?C?v]是哈密爾頓連通圖。由于

[eGB?C?v=n-3 2+9-5-t ≥n-3 2+9-5-7 >n-2-3 2+6]

根據(jù)引理1.3，[GB?C?v]是哈密爾頓連通圖，故[G]是哈密爾頓圖，矛盾。

（4）[GA]中沒(méi)有邊。在這種情況下，[G?M3N]，與定理?xiàng)l件矛盾。證明完成。

定理 2.2 設(shè)圖[G]是一個(gè)[n]階連通圖，[n>21]，[δG≥3]。如果[μG≥n-4]，[G≠L3n]或[G≠M(fèi)3n]，則[G]是哈密爾頓圖。

證明：根據(jù)引理1.1和定理2.2的條件，有[n-4≤μG≤][2m-n+1]，得到[m≥n-32+2]，因?yàn)閇δK1，n-1=1]，所以[G≠K1，n-1]。因此根據(jù)定理2.1，如果[G?L3n]或[G?M3n]，則圖[G]是哈密爾頓圖。

第一種情況[G?L3n]，根據(jù)引理1.4，如果[G]是[L3n]是一個(gè)子圖，且最小度[δG≥3]，則[μG<n-4]，產(chǎn)生矛盾。

第二種情況[G?M3n]，根據(jù)引理1.4，如果[G]是[M3n]是一個(gè)子圖，且最小度[δG≥3]，則[μG<]

[n-4]，產(chǎn)生矛盾。證明完畢。

3 結(jié)語(yǔ)

通過(guò)上述定理的證明，擴(kuò)充了一個(gè)圖是哈密爾頓圖的譜半徑條件，對(duì)后續(xù)研究圖的哈密爾頓性有很大幫助。在今后的科研工作中，將繼續(xù)研究圖的哈密爾頓性，除了最小度參數(shù)條件，還可以加入連通度、韌度等條件研究圖的哈密爾頓性的譜半徑條件。

［參考文獻(xiàn)］

［1］ Lu M ，Liu HQ，Tian F. Spectral Radius and Hamiltonion graphs［J］. Linear Algebra and its Applications， 2012，437：1670-1674.

［2］ 余桂東. 圖的哈密爾頓性的譜條件［J］. 應(yīng)用數(shù)學(xué)，2014，27（3）：588-595.

［3］ Nikiforov V. Spectral radius and Hamiltoncity of graphs with large minimum degree［J］. Czechoslovak Mathematical Journal，2016，66（3）：925-940.

［4］ Yu GD，F(xiàn)ang Y，F(xiàn)an YZ，et al. Spectral Radius and Hamiltonicity of graphs［J］. Discussiones Mathematicae Graph Theory，2019，39（4） ：951-974.

［5］ Jiang GS，Yu GD，F(xiàn)ang Y. Spectral conditions and Hamiltonicity of a balanced bipartite graph with large minimum degree［J］. Applied Mathematics and Computation，2019，356：137-143.

［6］ 劉珍珍，余桂東. 哈密爾頓圖的一些譜充分條件［J］. 安慶師范大學(xué)（自然科學(xué)版），2021，27（4）：75-79.

［7］ 余桂東，袁慧，張子杰. 帶有最小度的哈密爾頓圖的充分條件［J］. 安徽理工大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2022，42（5）：71-74.

［8］ 方怡，余桂東. 給定最小度和邊連通度的圖的最大無(wú)符號(hào)拉普拉斯譜半徑［J］. 安慶師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2021，27（1）：26-28.

［9］ 劉莉，袁慧，何煥. 無(wú)符號(hào)拉普拉斯譜半徑與圖的若干性質(zhì)［J］. 巢湖學(xué)院學(xué)報(bào)，2022，24（3）：52-55.

［10］ Zhao K W，Lin Y，Zhang P. A sufficient condition for pancyclic graphs［J］. Information Processing Letters，1993，109（17）： 991-996.

［11］ Chvatal V. On Hamiltons idears［J］. Journal of Combinatorial Theory， Series B， 1972，12：163-168.

［12］ Zhou Q N，Wang L G. Some sufficient spectral conditions on Hamilton-connected and traceable graphs［J］. Linear Algebra and its Applications， 2010，432：566-570.

責(zé)任編輯 孫 澗

［收稿日期］ 2024-04-10

［基金項(xiàng)目］ 國(guó)家自然科學(xué)基金（11871077）；安徽省高?？茖W(xué)研究重點(diǎn)項(xiàng)目“圖的哈密爾頓性研究”（2023AH052887）；省級(jí)研究生線下示范課程圖論（2022xxsfkc038）；校級(jí)研究生線下課程圖論（2021aqnuxxkc03）；院級(jí)質(zhì)量工程教學(xué)研究重點(diǎn)項(xiàng)目（tlpt2023jyzd006）

［作者簡(jiǎn)介］ 方怡（1992- ），女，碩士，銅陵職業(yè)技術(shù)學(xué)院基礎(chǔ)教學(xué)部講師，研究方向：代數(shù)圖論。