哈密尔顿图的谱半径条件

【摘 要】 设[G]是一个简单图，[G]的邻接矩阵是表示[G]顶点之间相邻关系的矩阵，它的最大特征值被定义为图的谱半径。一个包含图[G]中所有顶点的圈称为哈密尔顿圈，如果图[G]包含一个哈密尔顿圈，则称图[G]是哈密尔顿图。设[G]具有最小度条件，主要利用[G]的谱半径给出[G]是哈密尔顿图的充分条件。

【关键词】 连通图；哈密尔顿图；谱半径；最小度

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

〔中图分类号〕 O157.5 〔文献标识码〕 A 〔文章编号〕 1674 - 3229（2024）03 - 0030 - 03

0 引言

本文研究简单无向图。首先介绍图的符号表示，设[G=VG，EG]是一个[n]阶简单连通图，其顶点集[VG=v1，v2，…，vn]，定义[n=VG]为[G]的阶数，顶点[vi∈VG]的邻域定义为[NGvi]，表示与[vi]相连的点的集合。顶点[vi]的度[dGvi=NGvi]（简写为[di]），不失一般性，设[d1≤d2≤…≤dn]，记[d1，d2，…，dn]为[G]的度序列，[G]的最小度记为[δG]。定义[m=EG]为[G]的边数。设[G1]和[G2]是两个顶点不相交的简单图，其并图[G1⋃G2=VG1⋃VG2，EG1⋃EG2]，它们的联图[G1∨G2]是由[G1⋃G2]添加[G1]中每个顶点到[G2]中每个顶点的边构成的图。设点集[S⊆VG]，则[GS]表示由点集[S]产生的子图。记[Kn]为[n]阶完全图，[On=Kn]为[n]阶空图（不含边），[Kn，m=On∨Om]为完全二部图。

图[G]的谱半径记为[μG]，定义为图[G]的邻接矩阵的最大特征值。图[G]的邻接矩阵定义为[AG=aijn×n]，其中当[vi]，[vj]相邻时，[aij=1]，否则[aij=0] 。

哈密尔顿图的谱半径条件是图论中经典且很困难的问题。陆枚等［1］对图的边数条件进行优化，从而给出利用谱半径判断一个图是哈密尔顿图的充分条件，余桂东［2］利用补图的谱半径给出原图含有哈密尔顿路、哈密尔顿圈以及原图是哈密尔顿-连通图的一些谱条件。如果一个图是哈密尔顿图，那么它的最小度大于等于2，因此可以将图的最小度与图的哈密尔顿性紧密联系在一起，这又是后面学者研究的重点内容。Nikiforov［3］研究了带有最小度的图的哈密尔顿性的谱半径条件，余桂东等［4］进一步研究了带有最小度的图（平衡二部图）的哈密尔顿性的谱半径条件，随后江贵生等［5］、刘珍珍等［6］、余桂东等［7］进行了进一步研究。除了利用谱半径判断图的哈密尔顿性以外，方怡等［8］、刘莉等［9］利用无符号拉普拉斯谱半径判断图的一些性质。本文将对哈密尔顿图的谱半径条件进行进一步研究。

1 相关引理

引理1.1［10］ 设图[G]是一个[n]阶图，有[m]条边，则[μG≤2m-n+1]，当且仅当[G=Kn]或[G=K1，n-1]时等式成立。

引理1.2［11］ 设[G]是一个[n]阶图，满足度序列[d1≤]

[d2≤…≤dn]。假设不存在整数[s<n2]使得[ds≤s]，[dn-s≤n-s-1]同时成立，则图[G]是哈密尔顿图。

引理1.3［12］ 设[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］ 设[k≥1]，[n≥k32+k+4]，[G]是一个[n]阶图，最小度满足[δG≥k]，则

（1）如果[G]是[Mkn]的一个子图，则[μG<n-k-1]，

除非[G=Mkn]；

（2）如果[G]是[Lkn]的一个子图，则[μG<n-k-1]，

除非[G=Lkn]。

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

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

2 主要结论

定理 2.1 设图[G]是一个[n]阶图，[n>21]，[δG≥3]。如果[eG≥n-3 2+2]，

[G⊄L3n]或[G⊄M3n]，则图[G]是哈密尔顿图。

证明：假设图[G]满足上述条件但是图[G]不是哈密尔顿图。设[d1，d2，…，dn]是图[G]的度序列，根据引理1.2，存在一个整数[s<n2]，使得[ds≤s]且[dn-s≤n-s-1]，记[m]是图[G]的边数，显然

[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。]因为[eG≥n-3 2]

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

当[4≤s≤n-12]，其中[n>21]，通过直接计算，得到[f4=36-2n<0]，[fn-12=-n2+24n-634≤0]，产生矛盾。

当[s=3]，通过直接计算，得到[f3=14>0]。

因此，只要讨论当[s=3]时的情形。由于[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]，从这里可以计算出（1）中的不等式必须是等式，所以图[G]的度序列[（3，3，3，n-4，n-4，…，n-4，n-1，]

[n-1，n-1）]，将3个度为[3]的点记为[A]，[n-6]个度为[n-4]的点记为[B]，3个度为[n-1]的点记为[C]。这表明[G≅M3n]，与定理条件矛盾。

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

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

注意到任意[t]个[3]度点最多关联[3t]条边，任意[n-t]个点最多连接[n-t 2]条边，即当[G]有[t]个[3]度顶点时，至多构成[n-t 2+3t]条边。由于[eG≥n-3 2+2]，故[t≤3]，由度序列（1），得到图[G]恰有3个[3]度点。在这种情况下，只能减少[VB⋃C]中点的度数，即在[GB⋃C]中去边。接下来考虑下面2种情况。

第一种情况：[VA]中的点只与[VB⋃C]中一个点相连。在这种情况下，[G⊆L3N]，与定理条件矛盾。

第二种情况：[VA]中的点与[VB⋃C]中至少2个点相连。在这种情况下，需要考虑下面4种情况。

（1）[GA]中有3条边。在这种情况下，[GA=K3]是一个完全图，证明[G]是哈密尔顿图只需要证明[GB⋃C]是哈密尔顿连通图。由于

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

根据引理1.3，[GB⋃C]是哈密尔顿连通图，故[G]是哈密尔顿图，矛盾。

（2）[GA]中有2条边。 在这种情况下，[GA=P3]是一条路，[VB⋃C]中至少有2个点与[VA]中点相连。因此证明[G]是哈密尔顿图只需要证明[GB⋃C]是哈密尔顿连通图。由于

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

根据引理1.3，[GB⋃C]是哈密尔顿连通图，故[G]是哈密尔顿图，矛盾。

（3）[GA]中有1条边。 在这种情况下，[GA]中有一个独立的点[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]

根据引理1.3，[GB⋃C⋃v]是哈密尔顿连通图，故[G]是哈密尔顿图，矛盾。

（4）[GA]中没有边。在这种情况下，[G⊆M3N]，与定理条件矛盾。证明完成。

定理 2.2 设图[G]是一个[n]阶连通图，[n>21]，[δG≥3]。如果[μG≥n-4]，[G≠L3n]或[G≠M3n]，则[G]是哈密尔顿图。

证明：根据引理1.1和定理2.2的条件，有[n-4≤μG≤][2m-n+1]，得到[m≥n-32+2]，因为[δK1，n-1=1]，所以[G≠K1，n-1]。因此根据定理2.1，如果[G⊄L3n]或[G⊄M3n]，则图[G]是哈密尔顿图。

第一种情况[G⊆L3n]，根据引理1.4，如果[G]是[L3n]是一个子图，且最小度[δG≥3]，则[μG<n-4]，产生矛盾。

第二种情况[G⊆M3n]，根据引理1.4，如果[G]是[M3n]是一个子图，且最小度[δG≥3]，则[μG<]

[n-4]，产生矛盾。证明完毕。

3 结语

通过上述定理的证明，扩充了一个图是哈密尔顿图的谱半径条件，对后续研究图的哈密尔顿性有很大帮助。在今后的科研工作中，将继续研究图的哈密尔顿性，除了最小度参数条件，还可以加入连通度、韧度等条件研究图的哈密尔顿性的谱半径条件。

［参考文献］

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

［2］ 余桂东. 图的哈密尔顿性的谱条件［J］. 应用数学，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，Fang Y，Fan YZ，et al. Spectral Radius and Hamiltonicity of graphs［J］. Discussiones Mathematicae Graph Theory，2019，39（4） ：951-974.

［5］ Jiang GS，Yu GD，Fang 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］. 安庆师范大学（自然科学版），2021，27（4）：75-79.

［7］ 余桂东，袁慧，张子杰. 带有最小度的哈密尔顿图的充分条件［J］. 安徽理工大学学报（自然科学版）， 2022，42（5）：71-74.

［8］ 方怡，余桂东. 给定最小度和边连通度的图的最大无符号拉普拉斯谱半径［J］. 安庆师范大学学报（自然科学版），2021，27（1）：26-28.

［9］ 刘莉，袁慧，何焕. 无符号拉普拉斯谱半径与图的若干性质［J］. 巢湖学院学报，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.

责任编辑 孙 涧

［收稿日期］ 2024-04-10

［基金项目］ 国家自然科学基金（11871077）；安徽省高校科学研究重点项目“图的哈密尔顿性研究”（2023AH052887）；省级研究生线下示范课程图论（2022xxsfkc038）；校级研究生线下课程图论（2021aqnuxxkc03）；院级质量工程教学研究重点项目（tlpt2023jyzd006）

［作者简介］ 方怡（1992- ），女，硕士，铜陵职业技术学院基础教学部讲师，研究方向：代数图论。