可跡圖的譜半徑條件

方 怡，劉 琦，阮 佂，周 甫

圖G的度對角矩陣為D(G)=diag(dG(v2),…,dG(vn) )。圖G的鄰接矩陣定義為A(G)=(aij)n×n，其中當(dāng) vi，vj相鄰時，aij=1，否則aij=0。由于A(G)為實(shí)對稱矩陣，故其特征值均為實(shí)數(shù)，可進(jìn)行排序，稱A(G )的最大特征值為圖G的譜半徑，記為 μ(G)，與對應(yīng)的全正向量成為G的Perron向量。

如果圖G中任意兩點(diǎn)均有一條路連接，則稱圖G是連通的。如果圖G中有一條包含G中所有頂點(diǎn)的路，則稱這條路為哈密爾頓路；如果圖G含有哈密頓路，則稱圖G是可跡圖。對于哈密頓問題的研究是經(jīng)典圖論中一個非常困難的問題，近年來，譜圖理論應(yīng)用到這個問題，如文獻(xiàn)[1-6]。本文主要利用圖G補(bǔ)圖的譜半徑來刻畫圖G是可跡圖的充分條件，此時δ()G ≥k。

1 相關(guān)引理

對于一個整數(shù)k≥0，圖G的k閉包是指反復(fù)連接G中度之和不小于k的不相鄰的頂點(diǎn)對直到?jīng)]有這樣的頂點(diǎn)對為止所得的圖，記為Ck(G)，它是唯一的，并且圖Ck(G)中任意兩個不相鄰的點(diǎn)對u和v均滿足dCk(G)(u ) +dCk(G)(v)≤k-1。

引理1[7]設(shè)G是一個n階簡單圖，圖G含有一條哈密頓路當(dāng)且僅當(dāng)Cn-1(G)含有一條哈密頓路。

給定一個n階圖G，對于向量X∈Rn，如果存在一個從V(G )到X中的值的一一映射φ，使得?u∈V(G )，有 φ(u)=Xu，則稱X定義在G上。因此，由特征值的定義知，若X是A(G)的特征值μ對應(yīng)的特征向量，則當(dāng)且僅當(dāng)X≠0時，對于每一個v∈V(G)，有

下面的引理在文獻(xiàn)[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]設(shè)G是一個非空圖，則有

并且，如果G是連通的，當(dāng)且僅當(dāng)G是正則圖或二部半正則圖時等式成立。

證明 設(shè)X是圖G的一個單位Perron向量，設(shè)

由（1）式可得

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

如果圖G是連通的并且等式成立，有任意點(diǎn)v∈NG(s) ，Xv=Xt，任意點(diǎn) v∈NG(t)，Xv=Xs。 通過（1）式，得到圖G是正則圖或是二部半正則圖。如果圖G是dj正則圖，則 μ(G)=d；如果圖G是(Δ ,δ)-二部半正則圖，則 μ(G)=。

2 主要結(jié)論

設(shè)EPn是下面的一些n階圖，此時n為偶數(shù)：

(ii)G1∨G2，G1是 n-r階度為-r的正則圖，G2是有r個頂點(diǎn)的圖，此時1≤r≤。

定理1 設(shè)圖G是一個n階圖，n≥2k+2，k≥0。如果 δ(G )≥k，且

則圖G是可跡圖，除非G=Kk+1+Kn-k-1或G∈EPn且n=2k+2。

證明 設(shè)H=Cn-1(G )，根據(jù)引理1，如果H是可跡圖，則G也是可跡圖。現(xiàn)在假設(shè)H不是可跡圖，注意到H是G的(n -1)-閉包，因此H中任意兩不相鄰的點(diǎn)對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。 結(jié)合（3）式，有k+1 ≤ dHˉ(u )≤n-k-1 ，k+1≤ dHˉ(v)≤n-k-1，并且對任意uv∈E(Hˉ)，有

設(shè)f(x)=x(n -x)。當(dāng)k+1≤x≤n-k-1時，有f(x)≥f(k +1)（或 f(x)≥ f(n -k-1)），當(dāng)且僅當(dāng)x=k+1（或x=n-k-1）時等式成立。因此dHˉ(u) dHˉ(v) ≥ dHˉ(u)(n -dHˉ(u ) )≥(k +1)(n -k-1)，當(dāng)且僅當(dāng) dHˉ(u)=k+1 ，dHˉ(v)=n-k-1時等式成立。

通過引理1、Perron-Frobenius定理和定理1的假設(shè)，得到

接下來假設(shè)F是一個正則圖。對每一個點(diǎn)v∈V(F)，dF(v)=，并且 n=2k+2。如果 F=Hˉ，和上面的討論相似，Gˉ=Hˉ，因此G=H是度為-1的正則圖，這表明G∈EPn，這與定理?xiàng)l件矛盾。

所 以 Hˉ=F?Or，這 里 r=n- | V(F ) |，1≤r≤-1。 注 意 到 μ(Gˉ )=μ(Hˉ)=μ(F )，有Gˉ=F?F1，F(xiàn)1是從Or中加入一些邊得到的圖。因+1≤ ||V(F)≤n。

假設(shè)F是一個二部半正則圖，通過（3）式知F=Hˉ是一個完全二部圖，則此時 Hˉ=Kk+1,n-k-1。此G=Fˉ∨Fˉ1∈EPn，這與定理?xiàng)l件矛盾。

參考文獻(xiàn)：

[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.