带有最小度的哈密尔顿图的充分条件

余桂东，袁 慧，张子杰

(1.安庆师范大学数理学院，安徽 安庆 246133;2.合肥幼儿师范高等专科学校公共教学部，安徽 合肥 230013)

设G=(V(G),E(G))是n阶简单无向图，其顶点集为V=V(G)，边集为E=E(G)。e(G)=|E(G)|表示图G的边数。NG(v)表示由顶点v∈V(G)的邻点组成的集合，dG(v)=|NG(v)|表示顶点v的度。定义NG[v]=NG(v)∪{v}。若S是V(G)的非空子集，NG(S)表示与S中顶点相邻的所有顶点的集合。用δ(G)(简记为δ)来表示G中顶点的最小度，G+H表示G和H不交并，G∨H表示在G+H中把G的每个顶点和H的每个顶点连接起来得到的图。若S是V(G)的非空子集，则G[S]表示以S为顶点集、以G中两端点均在S中的边为边集的图。对于两个点不交的V(G)的非空子集S和T，G[S,T]表示以S∪T为顶点集，以G中所有一个端点在S中，另一个端点在T中的边为边集的二部图。对于非负整数n，若连续连接图G中度和至少为n的不相邻点对，直到没有这样的点对存在后，所得到的图称为图G的n-闭包，记为cln(G)。图G的n-闭包是唯一确定的，与所增加的边的次序无关，并且在cln(G)中任意不相邻点对u、v，有

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

设图G的顶点集为{v1,v2,…,vn}。图G的邻接矩阵为A(G)=[aij]n×n，当vi,vj相邻时，aij=1，否则aij=0。图G的度对角矩阵为D(G)=diag(d(v1),d(v2),…,d(vn))。图G的无符号拉普拉斯矩阵为Q(G)=A(G)+D(G)。A(G)的最大特征值称为图G的谱半径，记为ρ(G)。Q(G)的最大特征值称为图G的无符号拉普拉斯谱半径，记为q(G)。图G的一条途径是指W=v0e1v1e2v2…ekvk，如果途径内部边互不相同，且起点和终点相同，则称为闭迹。如果一条闭迹的起点和内部顶点互不相同，则称为圈。如果一个圈包含图的所有顶点，则称为哈密尔顿圈。如果图G包含一个哈密尔顿圈，则图G是哈密尔顿图。

长期以来，判断一个图是否是哈密尔顿图是NP-完全问题。许多学者都在致力于寻找判断一个图是哈密尔顿图的充分条件。文献[1]2 171给出了当δ(G)≥1时，图G是哈密尔顿图的谱半径充分条件。文献[2]改进了文献[1]2 171中最小度条件，研究了当δ(G)≥2时，图G是哈密尔顿图的谱充分条件。文献[3]2 258通过添加大的最小度条件，即δ(G)≥k≥1，探究图G是哈密尔顿图的谱充分条件。文献[4]不仅改进文献[3]2 258中大的最小度条件，并且优化了谱下界。文献[5]27研究了δ(G)≥k≥1时，图G是哈密尔顿图的谱充分条件。受以上文献的启发，与文献[5]30中证明方法相似，给出了带有大的最小度图是哈密尔顿图的谱半径和无符号拉普拉斯谱半径充分条件。本文改进了文献[5]27中最小度条件，得到的边数条件、谱半径和无符号拉普拉斯谱半径条件均优化了文献[5]28中的条件。

1 预备知识

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

引理1[6]472图G是哈密尔顿图当且仅当cln(G)是哈密尔顿图。

引理3[3]2262设2≤l≤k-1，F是阶数为k的(k-l)正则图，则Kl∨(F+Kn-l-k)是哈密尔顿图。

引理5[5]29设图G是n阶图有m条边，且最小度为δ，则

2 主要结果

定理1设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。

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

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

证明断言2 首先，证明dk+1≥n-3k2-3k-1。假设dk+1

矛盾。故假设不成立，因此有dk+1≥n-3k2-

3k-1。

接下来证明H[{vk+1,…,vn}]=Kn-k。因为对于任意顶点对vi,vj，k+1≤i,j≤n,有

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

由H=cln(G)的定义知，对于任意顶点对vi,vj均相邻，k+1≤i,j≤n,即H[{vk+1,…,vn}]=Kn-k。

设X1={v1,…,vk}。因为d1=d2=…=dk=k，|X1|=k，则X1的每个顶点至少与{vk+1,…,vn}中的一个顶点相邻。设X2⊆NH(X1)∩{vk+1,vk+2,…,vn}。对于任意x∈V(H)，令NX2(x)=

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

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

证明断言3 假设H[X1,X2]≠Kk,l，则存在不同顶点u,v∈X1，w∈X2，使得w∈NX2(u)NX2(v)。

因为dH(w)≥n-k，则

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

由闭包定义知w∈NX2(v)，这与w∈NX2(u)NX2(v)矛盾。假设不成立，因此H[X1,X2]=Kk,l。

结合以上3个断言，若l=1，则H=K1∨(Kk+Kn-k-1)；若l=k，则H=Kk∨(Kn-2k+kK1)； 若2≤l≤

k-1的情况，应用引理3知H是哈密尔顿图，与假设矛盾，证明完毕。

实际上，文献[5]30也给出了与定理1相似的定理。

定理2[5]30设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优化了定理2。

定理3设图G是n阶图， 其中n≥6k2+6k+2，δ(G)≥k≥2。若

则图G是哈密尔顿图，除非cln(G)=K1∨(Kk+

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

证明根据引理4和引理6，得到

假设G不是哈密尔顿图，则根据定理1知，cln(G)=K1∨(Kk+Kn-k-1)或者cln(G)=Kk∨(Kn-2k+kK1)，证明完毕。

定理4[5]27设图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优化了定理4。

定理5设G是n阶图， 其中n≥6k2+6k+2，δ(G)≥k≥2。若

则图G是哈密尔顿图，除非cln(G)=K1∨(Kk+

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

证明 根据引理5，得到

假设G不是哈密尔顿图，则根据定理1知，cln(G)=K1∨(Kk+Kn-k-1)或者cln(G)=Kk∨(Kn-2k+kK1)，证明完毕。

定理6[5]28设图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优化了定理6。

3 结论

本文利用图的闭包以及度序列，首先得到带有大的最小度图是哈密尔顿图的边数条件，然后根据边数与谱之间的关系，给出带有大的最小度图是哈密尔顿图的谱、无符号拉普拉斯谱充分条件。