刘珍珍，余桂东

（安庆师范大学数理学院，安徽 安庆 246133）

令图G是顶点集V(G)={v1,v2,v3,…,vn}和边集E(G)={e1,e2,e3,…,en}的连通图，其中=m。E(G)中的元素{u,v}(u≠v)称为G的边，边{u,v}简记uv。记=(V(G),为G=(V(G),E(G))的补图，其中补图的边集为，x≠y,xy∉E(G)}。若vi∈V(G)，令di=d(vi)表示顶点vi的度，并设(d1,d2,d3,…,dn)是图G的度序列，其中d1≤d2≤d3≤…≤dn。为了方便起见，用δ(G)或δ表示G的最小度，用Δ(G)或Δ表示G的最大度。设Ks,t是一个完全二部图，它的两个分部分别有s、t个顶点。记Kn、K1,n-1和Cn分别为n阶完全图、星图和圈。设e为图G中的一条边，记G-e为图G中删去边e所得的图。v为图G中的一个点，记G-v是图G中删去点v以及与v相关联的边所得的图。

简单图G和H的并是点集为V(G)⋃V(H)，边集为E(G)⋃E(H)的图，记作G⋃H。如果G和H不交，它们的并称为不交并，通常记作G+H。k个图G的不交并用kG表示。G+H中通过加边使G中每一个点和H的每一个点相连，这样得到的图称作G和H的联，用G∨H表示。令A(G)表示图G的邻接矩阵，这里A(G)是n阶矩阵(aij)，如果顶点vi和vj相邻，那么aij=1，否则aij=0。显然，A(G)是非负实对称矩阵，它所有的特征值都是实数。称A(G)的最大特征值为图G的谱半径，用μ(G)来表示。设D(G)=dig(d1,d2,d3,…,dn)是图G的度对角矩阵，定义图G的无符号拉普拉斯矩阵Q(G)=D(G)+A(G)，称Q(G)的最大特征值为图G的无符号拉普拉斯谱半径，用q(G)表示。

如果图G含有图中所有顶点的路，则称这个路为哈密尔顿路，而闭合的哈密尔顿路称为哈密尔顿圈。如果图G中含有哈密尔顿圈，则称G是哈密尔顿图。判定所给的图是哈密尔顿的，这是NP-困难的问题。因为图的谱容易计算，所以常常利用图的谱去研究图的结构性质，将验证变成计算，从而提供了一种容易且高效的判定方法。关于哈密尔顿图的谱条件的成果有很多。文献[1]基于图与补图的谱半径给出了一个图是哈密顿图的充分条件；文献[2]基于图的谱半径给出了一个图含有哈密尔顿路的充分条件；文献[3]基于图的补图的无符号拉普拉斯谱半径给出了哈密尔顿圈存在的充分条件；文献[4]得到了二部图是哈密尔顿图的谱半径充分条件，并且给出了基于无符号拉普拉斯半径的哈密尔顿图的充分条件；文献[5]给出了哈密尔顿图与可迹图的一些充分条件；更多相关结论可参考文献[6-9]。受文献[5]的启发，本文分别利用图G及其补图的谱半径和无符号拉普拉斯谱半径给出了G是哈密尔顿图的一些谱充分条件。

1 准备工作

给定n阶图G，对于向量x∈Rn，如果存在一个从V(G)到x中的分量的一一映射φ，对于任意的u∈V(G)，有φ(u)=xu，这时称x定义在G上。由特征值的定义可知，如果x是A(G)的特征值μ对应的一个特征向量，则当且仅当x≠0时，x中的元素xu与点μ对应，有

这里的NG(v)定义为v在G中的邻集，式（1）称为图G的特征方程。

如果x是Q(G)的特征值q对应的一个特征向量，则当且仅当x≠0时，x中的元素xu与点u对应，有

式（2）称为图G的无符号拉普拉斯特征方程。

如果连续地连接连通图G中度和大于等于k的不相邻点对，直到没有这样的点对存在后，那么所得到的图称为图G的k-闭包，常用Ck(G)表示。这样得到的k-闭包是唯一的，与所增加边的次序无关。在Ck(G)中，任意一对不相邻顶点对u和v都有dH(u)+dH(v)≤k-1。

下面给出引理和定理中所用到的一些特殊图。

（1）设M=K7，N=8K1，x1,x2∈V(M)，y1,y2∈V(N)，从M∨N中删去x1y1、x2y2两条边得到的图为G1，从M∨N中删去x1y1、x1y2两条边得到的图为G2。

引理1[5]设图G是阶数为n(≥7)，边数为m，最小度δ≥6的简单图。如果，则G是哈密尔顿图，除非G∈NC。

引理2[10]设图G是具有m条边的n阶连通图，则有，当且仅当G=Kn或者G=K1,n-1时等式成立。

引理3[11]设图G是具有m条边的n阶简单图，则有，如果G是连通的，当且仅当G=Kn或者G=K1,n-1时等式成立；如果G是不连通的，当且仅当G=Kn-1+v时等式成立。

引理4[12]图G含一个哈密尔顿圈，当且仅当Cn(G)含一个哈密尔顿圈。

2 主要结果

定理1设图G是顶点数为n(≥7)，边数为m，最小度δ≥6的连通图，如果μ(G)≥，则G是哈密尔顿图。

证明由定理条件和引理2知，当μ(G)=时，显然Kn是哈密尔顿图，且K1,n-1不是哈密尔顿图，通过计算μ(K1,n-1)=恒成立。当μ(G)＞时，由引理2知≤μ(G)＜，即m＞+8；由引理1可知G是哈密尔顿图，除非G∈NC。

如果G=K6∨7K1，设x=(x1,x2,…,x13)T是μ(G)的单位特征向量，于是有

由式（1）知，所有度为6的点都有相同的分量，记为X1；所有度为12的点都有相同的分量，记为X2，则由特征方程式（3）有

令f(x)=det(xI-SA(G))，μ(G)是f(x)=0的 最 大 根，经 过 计 算，μ(G)=9.446 2＜=9.6954，用相同的方法计算NC中其他图的谱半径，如表1所示。

表1 NC中的谱半径

根据表1可知，NC中所有图的特征值都满足。

定理2设图G是顶点数为n(≥7)，边数为m，最小度δ≥6的连通图。如果

则G是哈密尔顿图，除非G=K6∨7K1。

证明由定理条件和引理3知，当q(G)=+2n-8时，显然Kn是哈密尔顿图，且K1,n-1不是哈密尔顿图，但δ(K1,n-1)=1，δ(Kn-1+K1)=0，这与δ(G)≥6矛盾。

当q(G)＞+2n-8时，由引理3可知

故m＞+8，再由引理1可知G是哈密尔顿图，除非G∈NC。

如果G=K6∨7K1，设x=(x1,x2,…,x13)T是q(G)的单位特征向量，于是有

由式（2）知，所有度为6的点都有相同的分量，记为X1；所有度为12的点也都有相同的分量，记为X2，则由特征方程（4）有

令g(x)=det(xI-SQ(G))，q(G)是g(x)=0的最大根，经过计算，q(G)=20.000 0＞+2n-8=19.8333，但是G=K6∨7K1不是哈密尔顿图，用相同的方法计算NC中其他图的无符号拉普拉斯谱半径，如表2所示。

表2 NC中无符号拉普拉斯谱半径

根据表2，NC中所有图的无符号拉普拉斯谱半径都满足q(G)＜+2n-8。。

定理3设图G是顶点数为n(≥7)，边数为m，最小度δ≥6的连通图。如果

则G是哈密尔顿图。

证明若G不是哈密尔顿图，设H是图G的n-闭包。从而由引理4可知，H不是哈密尔顿图。根据H的构造又知，在H中任意一对不相邻的顶点对u和v，dH(u)+dH(v)≤n-1都成立。设是H的补图，这样每一条边，都 有dHˉ(u)+dHˉ(v)≤n-2-dH(u)+n-2-dH(v)≥n-3，所以

根据文献[13]中的Hofmeister不等式，可以得到

由假设H不是哈密尔顿图，从而由引理1可知，H∈NC。用相同的方法计算NC中其他图的补图的谱半径，如表3所示。

表3 NC中的补图的谱半径

续表3

根据表3，NC中所有图的补图的谱半径都满足，与条件矛盾。因此，最初的假设不成立，则G是哈密尔顿图。

3 总结

本文主要从文献[5]所给的哈密尔顿图的边数条件出发，考虑图的哈密尔顿性的边数条件与极端谱之间的联系，进一步分别利用图及其补图的谱半径和无符号拉普拉斯谱半径来刻画图的哈密尔顿性。研究结果不仅丰富了图的哈密尔顿性的研究，而且推动了图的哈密尔顿问题在代数方法上的研究。另外，对于哈密尔顿图的谱充分条件可以加入其他参数条件，进而可能会得到与其相关的更好结论，这是我们下一步研究工作的重点。