图的周长的谱刻画

赵 力，许秋晨，叶淼林

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

图的哈密尔顿问题自1856年被英国数学家Hamilton提出后受到了众多学者的关注，很多图论领域的学者都利用图的谱来刻画图的哈密尔顿性。2013年，文献[1]提出了图是哈密尔顿或者可迹的无符号拉普拉斯谱充分条件；2015年，文献[2]利用谱分析方法将这一结论的界进一步缩小，并且在平衡二部图中给出了一个图是哈密尔顿或者可迹的谱充分条件，还进一步提出了图是哈密尔顿的或者可迹的边充分条件；文献[3]提出了带最小度条件的哈密尔顿图的边充分条件，在研究过程中发现该条件与图的谱相结合时，可以更好地刻画图的哈密尔顿性。因此，本文基于这个边条件用谱来刻画图的哈密尔顿性。

文中所涉及的图均为有限无向的简单图，图中最长圈的长度称作周长，记作c(G)。如果n阶图G周长为n，那么称G是哈密尔顿图。如果图G的顶点集V(G)可以被划分为两个互不相交的子集X和Y，使得V(G)=X⋃Y，并且任意一条边uv∈E(G)都满足u、v不在同一个子集X（或Y）中，则称G为二部图。用K s,t表示两个分部的阶数分别是s和t的完全二部图，即两个分部内部没有边，但每个分部的点与另一个分部的所有点都相连。设G、H是两个不相交的图，用G⋃H表示两个图的并，其中G⋃H中的点集为V(G)⋃V(H)，边集为E(G)⋃E(H)；用G∨H表示两个图的联图，即在图G与图H的基础上再添加上G中所有点与H中所有点所连接成的边。用G-e表示在G中删掉一条边e得到的图。文中没有提到的符号和术语参考文献[4]。

令λ1(G)≥λ2(G)≥λ3(G)≥…≥λn(G)是图G的邻接矩阵A(G)的所有特征值，记λ(G):=λ1(G)是图G的谱半径。令q1(G)≥q2(G)≥q3(G)≥…≥q n(G)是图G的无符号拉普拉斯矩阵Q(G)的所有特征值，记q(G):=q1(G)是图G的无符号拉普拉斯谱半径。在本文中定义一个特殊的n阶图W n,k,c，它是由一个c-k-1阶的完全图K c-k+1通过增加n-( )c-k-1个孤立点，且这些孤立点都与K c-k+1中相同的k个点相连构成的。注意到，在图W n,k,c中c(W n,k,c)=c，边数为

记G1和G2是两个特殊的图，令X=K7，Y=8K1，x1,x2∈V(X)，y1,y2∈V(Y)，其中G1是在X∨Y的基础上删掉x1y1，x2y2两条边得到的，G2是在X∨Y的基础上删掉x1y1，x1y2两条边得到的。为了方便起见，定义一个新的图类：

1 主要引理

给定n阶图G，对实数域上的n维向量X，如果存在一个从V(G)到X的一一映射φ，对于任意的u∈V(G)，有φ(u)=X u，则称X定义在G上。由特征值的定义可知，若X是A(G)的特征值λ对应的一个特征向量，则当且仅当X≠0时，对于每一个v∈V(G)，有

若X是Q(G)的特征值q对应的一个特征向量，则当且仅当X≠0时，对于每一个v∈V(G)，有

引理1[5]设G是n阶2-连通图，如果c(G)=c≤n-1，那么

引理2[6]设G是具有m条边的n阶连通图，则有λ(G)≤ 2m-n+1，当且仅当G=K n或G=K1,n-1时，等式成立。

引理3[7]设G是具有m条边的n阶简单图，则有

若G是连通的，则当且仅当G=K n或G=K1,n-1时，等式成立；若G是不连通的，则当且仅当G=K n-1+v时，等式成立。

引理4[3]设G是n(n≥7)阶，最小度δ(G)≥6的简单图，如果，那么G包含一个哈密尔顿圈，除非G⊆NC。

引理5[8]如果G-uv是通过在一个连通图中删去uv这条边得到的，那么λ( )

G-uv≤λ(G)。

2 主要结论

定理1设G是n阶2-连通图，如果c(G)=c≤n-1，那么

证明假设对n阶2-连通图G，有

显然这与引理1矛盾。

类似地，假设

显然这与引理1矛盾。

与周长c(G)≤n-1对应的是周长c(G)=n，即图G是一个哈密尔顿图。接下来给出δ(G)≥6的图G是哈密尔顿的谱条件。

定理2G是n(n≥7)阶，最小度δ(G)≥6的简单图，

证明假设对n阶连通图G，有λ(G)≥n2-8n+31成立，由引理2知，2m-n+1≥λ(G)，即将λ的值带入得到，由引理4可知，G包含一个哈密尔顿圈，除非G⊆NC。

接下来，采用求谱半径的方法（见例1），求出在NC中所有图的谱半径和无符号拉普拉斯谱半径，如表1所示。值得说明的是，对G1、G2，(8K1∨2K1-e)∨K5都在某一个图中删去一条边，由引理6可知，λ(K7∨8K1)≥λ(G1)，λ((8K1∨2K1)∨K5)≥λ((8K1∨2K1-e)∨K5)，λ(K7∨8K1)≥λ(G2)。因此，只需计算(8K1∨2K1)∨K5，( )

表1 NC的谱半径

8K1∨2K1∨K5的谱半径。

续表1

将图的阶数n=13,14,15,16,17代入和中，可以得到图的不同阶数对应的谱半径如表2所示。

表2 不同阶数对应的谱半径

通过对比发现q(K6∨7K1)=20，因此定理2成立。

下面通过例1给出计算（周长c≤n-1）的2-连通图的谱半径的方法。

例1当c为偶数时，证明：

证明（i）记X1是中度为的点构成的点集，Y1是中度为n-1的点构成的点集。设X是属于其谱半径的特征向量。对任意的i,j∈X1，有x i=x j；对任意的i,j∈Y1有y i=y j。令x=x i,i∈X1；y=y i,i∈Y1，由式（1），有

将式（3）转换成矩阵方程(λI-B)X=0，其中，X=(x,y)T，

令f(x):=det(x I-B)，则，可得f(x)的最大根为

即

（ii）设X′是属于其谱半径的特征向量，由式（2）及类似（i）中的分析，有

将式（4）转换成矩阵方程(q I-B′)X′=0，其中X′=(x,y)T，

令g(x):=det(x I-B′)，则，可得g(x)的最大根

3 结束语

综上所述，本文从哈密尔顿图的边数条件出发，将哈密尔顿图边数条件与谱极值问题相结合，给出了周长为c的2-连通图的谱半径上界，刻画了哈密尔顿图的谱充分条件。与文献[3]中的边条件相比，排除了绝大部分满足边数条件的图，将图的谱与周长相结合，而不仅仅是与哈密尔顿性相结合。研究结果不仅丰富了图的哈密尔顿性的研究，还推动了图的周长问题在代数方法上的研究。如果能找到图的一个最长圈（譬如长为n-1的圈），那么只需找到一个不在圈上的点，通过加边手段，使该点的度大于或者这个点与圈上的相邻两点相连即可找到一个新的哈密尔顿圈。这样便可以从周长的角度刻画图的哈密尔顿性，从而推进图的哈密尔顿性的研究。今后将探讨文献[9]中的Woodall猜想是否能用在求解图的哈密尔顿问题或最长圈问题中，以优化本文中的一些结论。