无符号拉普拉斯谱半径与图的哈密尔顿性

何 焕，王礼想，叶淼林

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

图G的邻接矩阵为A(G)=(aij)n×n，如果vivj∈E，则aij=1，否则aij=0，i,j=1,2,3,…,n。图G的度对角矩阵为D(G)=diag(d(v1),d(v2),d(v3),…,d(vn))，因此图G的无符号拉普拉斯矩阵为Q(G)=D(G)+A(G)。显然A(G)，Q(G)是实对称矩阵，所以其特征值均为实数且可以排序。A(G)的最大特征值λ(G)称为G的谱半径。Q(G)的最大特征值q(G)称为图G的无符号拉普拉斯谱半径。如果图G中任意两个点之间均能找到一条哈密尔顿路，则称G是哈密尔顿-连通图。如果图G中从任意点出发均能找到一条哈密尔顿路，则称G是从任意点出发可迹的。若连续连接图G中度和不小于k的不相邻点对，直到没有这样的点对存在，所得到的图称为G的k-闭包，记作Ck(G)。图G的k-闭包是唯一确定的，与所增加边的次序无关，并且在Ck(G)中任意不相邻点对u,v，均有

图的哈密尔顿问题一直是图论的热点问题，也是NP-完全问题。图的谱不但能够很好的反映图的结构性质且便于计算，所以图的谱理论被广泛用来解决此类问题。利用图的谱半径和无符号拉普拉斯谱半径来刻画图的哈密尔顿性取得了很多成果，如李斌龙等[2]给出了简单图和平衡二部图是可迹的和哈密尔顿的（无符号拉普拉斯）谱充分条件。余桂东等[3-4]研究了具有较大最小度的平衡二部图是可迹的和哈密尔顿的谱充分条件，以及利用谱半径和无符号拉普拉斯谱半径去刻画图的泛圈性的充分条件；周倩楠等[5]研究了具有较大最小度的图是哈密尔顿-连通的无符号拉普拉斯谱充分条件。徐奕等[6]分别借助图的大小、谱半径和无符号拉普拉斯谱半径给出了图是哈密尔顿-连通的一些充分条件。此外，周波[7]利用补图的无符号拉普拉斯谱半径给出了图存在哈密尔顿路和哈密尔顿圈的充分条件。而利用补图的无符号拉普拉斯谱半径去刻画具有较大最小度的图是哈密尔顿-连通问题至今还缺乏研究。受此启发，本文利用补图的无符号拉普拉斯谱半径给出了具有较大最小度的图分别是哈密尔顿的、哈密尔顿-连通的以及从任意点出发可迹的的充分条件。

1 预备知识

引理1[2]设G是一个边集非空的图，则λ(G)≥若G是连通图，当且仅当G是正则图或二部半正则图时等号成立。对引理1进行扩展，使其适用范围从邻接矩阵到无符号拉普拉斯矩阵。

引理2设G是n阶连通图，则q(G)≥2λ(G)，当且仅当G是正则图时等号成立。

下面给出图的哈密尔顿性与图闭包的哈密尔顿性间关系，以及特殊条件下正则图的哈密尔顿性。

引理4[2]设G是n阶图，G是哈密尔顿图当且仅当Cn(G)是哈密尔顿图。

引理5[1]当k≥2时，任意2k+1阶k-正则图都是哈密尔顿图。

引理6[8]设G是n阶图，G是哈密尔顿-连通图当且仅当Cn+1(G)是哈密尔顿-连通图。

引理7[9]（1）设t≥3和图G是2t阶不同构于Kt,t的t-正则图，则G是哈密尔顿-连通图。

（2）设t≥4且为偶数，G是2t+1阶t-正则图，则G是哈密尔顿-连通图。

引理8[1]设G是n阶图，G从任意一点出发都是可迹的当且仅当G∨K1是哈密尔顿-连通图。

2 主要结果

周波[7]利用补图的无符号拉普拉斯谱半径给出了简单图存在哈密尔顿路和哈密尔顿圈的充分条件。由于图的最小度与图的疏密性有关，因此本文在文献[7]的基础上添加了较大最小度这个条件，并运用新的方法得出了新结论，该结论的谱条件范围更精确且适用范围更优于文献[7]中的结论，并且在此基础上讨论了图的哈密尔顿-连通性和从任意点出发可迹的性质。

由引理3和Perron-Frobenius定理知

3 结论

本文系统研究了图的哈密尔顿性，主要是利用图的闭包思想将原图不容易解决的问题转化为补图的闭包来解决，再结合计算出的补图的谱半径的上界，得出原图的哈密尔顿性。本文的研究方法为挖掘哈密尔顿图的谱充分条件提供了一个新思路。