可迹图的谱半径条件

方 怡，刘 琦，阮 佂，周 甫

图G的度对角矩阵为D(G)=diag(dG(v2),…,dG(vn) )。图G的邻接矩阵定义为A(G)=(aij)n×n，其中当 vi，vj相邻时，aij=1，否则aij=0。由于A(G)为实对称矩阵，故其特征值均为实数，可进行排序，称A(G )的最大特征值为图G的谱半径，记为 μ(G)，与对应的全正向量成为G的Perron向量。

如果图G中任意两点均有一条路连接，则称图G是连通的。如果图G中有一条包含G中所有顶点的路，则称这条路为哈密尔顿路；如果图G含有哈密顿路，则称图G是可迹图。对于哈密顿问题的研究是经典图论中一个非常困难的问题，近年来，谱图理论应用到这个问题，如文献[1-6]。本文主要利用图G补图的谱半径来刻画图G是可迹图的充分条件，此时δ()G ≥k。

1 相关引理

对于一个整数k≥0，图G的k闭包是指反复连接G中度之和不小于k的不相邻的顶点对直到没有这样的顶点对为止所得的图，记为Ck(G)，它是唯一的，并且图Ck(G)中任意两个不相邻的点对u和v均满足dCk(G)(u ) +dCk(G)(v)≤k-1。

引理1[7]设G是一个n阶简单图，图G含有一条哈密顿路当且仅当Cn-1(G)含有一条哈密顿路。

给定一个n阶图G，对于向量X∈Rn，如果存在一个从V(G )到X中的值的一一映射φ，使得∀u∈V(G )，有 φ(u)=Xu，则称X定义在G上。因此，由特征值的定义知，若X是A(G)的特征值μ对应的特征向量，则当且仅当X≠0时，对于每一个v∈V(G)，有

下面的引理在文献[1]中可见，但是并没有被证明，为了更好地理解，我们给出它的证明。

㊸Prasenjit Duara，Why is History Antitheoretical?Modern China，Vol．24，No．2．Symposium:Theory and Practice in Modern Chinese History Research．Paradigmatic Issues in Chinese Studies，Part V(Apr．，1998)，pp．105 ～120．

引理2[1]设G是一个非空图，则有

并且，如果G是连通的，当且仅当G是正则图或二部半正则图时等式成立。

证明 设X是图G的一个单位Perron向量，设

由（1）式可得

因此 μ(G)2XsXt≥d(s) d(t) XsXt。

如果图G是连通的并且等式成立，有任意点v∈NG(s) ，Xv=Xt，任意点 v∈NG(t)，Xv=Xs。 通过（1）式，得到图G是正则图或是二部半正则图。如果图G是dj正则图，则 μ(G)=d；如果图G是(Δ ,δ)-二部半正则图，则 μ(G)=。

2 主要结论

设EPn是下面的一些n阶图，此时n为偶数：

(ii)G1∨G2，G1是 n-r阶度为-r的正则图，G2是有r个顶点的图，此时1≤r≤。

定理1 设图G是一个n阶图，n≥2k+2，k≥0。如果 δ(G )≥k，且

则图G是可迹图，除非G=Kk+1+Kn-k-1或G∈EPn且n=2k+2。

证明 设H=Cn-1(G )，根据引理1，如果H是可迹图，则G也是可迹图。现在假设H不是可迹图，注意到H是G的(n -1)-闭包，因此H中任意两不相邻的点对u，v度的和最多是n-2，即对任意uv∈E(Hˉ)，有

由于dH(u)≥dG(u )≥k，dH(v)≥dG(v) ≥k，得到dHˉ(u )≤n-k-1，dHˉ(v) ≤n-k-1。 结合（3）式，有k+1 ≤ dHˉ(u )≤n-k-1 ，k+1≤ dHˉ(v)≤n-k-1，并且对任意uv∈E(Hˉ)，有

设f(x)=x(n -x)。当k+1≤x≤n-k-1时，有f(x)≥f(k +1)（或 f(x)≥ f(n -k-1)），当且仅当x=k+1（或x=n-k-1）时等式成立。因此dHˉ(u) dHˉ(v) ≥ dHˉ(u)(n -dHˉ(u ) )≥(k +1)(n -k-1)，当且仅当 dHˉ(u)=k+1 ，dHˉ(v)=n-k-1时等式成立。

通过引理1、Perron-Frobenius定理和定理1的假设，得到

接下来假设F是一个正则图。对每一个点v∈V(F)，dF(v)=，并且 n=2k+2。如果 F=Hˉ，和上面的讨论相似，Gˉ=Hˉ，因此G=H是度为-1的正则图，这表明G∈EPn，这与定理条件矛盾。

所 以 Hˉ=F⋃Or，这 里 r=n- | V(F ) |，1≤r≤-1。 注 意 到 μ(Gˉ )=μ(Hˉ)=μ(F )，有Gˉ=F⋃F1，F1是从Or中加入一些边得到的图。因+1≤ ||V(F)≤n。

假设F是一个二部半正则图，通过（3）式知F=Hˉ是一个完全二部图，则此时 Hˉ=Kk+1,n-k-1。此G=Fˉ∨Fˉ1∈EPn，这与定理条件矛盾。

参考文献：

[1]LI B，NING B.Spectral analogues of Erdo’s and Moon-Moser’s theorems on Hamilton cycles[J].Linear Multilinear Algebra，2016，64(11)：2252-2269.

[2]FIEDLER M，NIKIFOROV V.Spectral radius and Hamiltonicity of graphs[J].Linear Algebra and Its Applications，2010，432(9)：2170-2173.

[3]FAN Y Z，YU G D.Spectral condition for a graph to be Hamiltonian with respect to normalized Laplacian[J].arXiv preprint arXiv：1207.6824，2012.

[4]LU M，LIU H Q，TIAN F.Spectral radius and Hamiltonian graph[J].Linear Algebra and Its Applications，2012，437(7)：1670-1674.

[5]NING B，LI B.Spectral radius and traceability of connected claw-free graphs[J].Filomat，2016，30(9)：2445-2452.

[6]NIKIFOROR V.Spectral radius and Hamiltonicity of graphs with large minimum degree[J].Czechoslovak Mathematical Journal，2016，66(3)：925-940.

[7]BONDY J A，CHVATAL V.A method in graph theory[J].Discrete Mathematics,1976，15(2)：111-135.