可跡圖的譜半徑條件

方 怡，劉 琦，阮 佂，周 甫

圖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也是可跡圖?，F在假設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.