哈密爾頓-連通圖的拉普拉斯譜充分條件

劉 琦，葉淼林

（安慶師范大學數(shù)學與計算科學學院，安徽安慶246133）

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

引理1[8-9]一個n階圖G是哈密爾頓-連通圖，當且僅當也是哈密爾頓-連通圖。

引理2[10]設G是一個n階圖，則。由引理2可直接得到推論1。

引理3[7]設G是一個n(≥5)階連通圖，最小度δ(G)≥2。若，則G是哈密爾頓-連通圖，除非

下面給出本文的主要結(jié)論及證明。

證明 設H=Cn+1(G)。如果H=Kn，則H是哈密爾頓-連通圖，由引理1知G也是哈密爾頓-連通圖，這樣結(jié)論成立。假設H≠Kn，且H不是哈密爾頓-連通圖，則由引理1知G也不是哈密爾頓-連通圖。注意到H中任意兩不相鄰的兩點u,v均滿足則Hc中任意邊uv均滿足由引理 2

(5.1)若Gc是由Hc添加一條邊構(gòu)成的圖，則或

(5.2)若Gc是由Hc添加兩條或兩條以上的邊構(gòu)成的圖，則由推論1知Gc只可能是由添加邊構(gòu)成的圖，且不為其子圖。

(5.2.1)若Gc是由Hc添加兩條邊構(gòu)成的圖，則或

(5.2.2)若Gc是由Hc添加3條或3條以上的邊構(gòu)成的圖，則由(5.2.1)推論1知Gc只可能是由或添加邊構(gòu)成的圖，且有，矛盾。

(7)若 H=K4∨(K1,3+K2)，則 Hc=4K1+((K1+K3)∨ 2K1)，且，e(Hc)=11，由 引 理 2得，則 有 110=n(2n-9)≥這樣Hc=Gc,即G=H=K4∨(K1,3+K2)，或Hc是Gc的真生成子圖，即Gc是由Hc添加邊構(gòu)成的圖。

(7.1)若Gc是由Hc添加一條邊構(gòu)成的圖，則Gc是2K1+K2+((K1+K3)∨2K1)或3K1+(((K1+K3)∨ 2K1)?P2)或4K1+((K3?P2)∨ 2K1)或4K1+((K1+K3)∨ K2)。

若 Gc是 2K1+K2+((K1+K3)∨ 2K1)，則，由引理2得，則有，由推論1知，此時

若Gc是，則，由引理2得矛盾。

(7.2)若Gc是由Hc添加兩條或兩條以上的邊構(gòu)成的圖。由推論1與(7.1)知，此時n(2n-9)，矛盾。

(8.1)若Gc是由Hc添加一條邊構(gòu)成的圖，則Gc是或或K1+或

若 Gc=2K1+(P3+K5), 則，由 引 理 2得，此時由推論 1知 G=K2∨(K1+K2)∨5K1=5K1∨ (K1+K2)∨ K2。

若 Gc=2K1+(K2+(K5?P2))，則，由引理2得，矛盾。

(8.2)若Gc是由Hc添加兩條或兩條以上的邊構(gòu)成的圖，則由推論1與(8.1)知，Gc只可能是由K1+(2K2+K5)添加邊構(gòu)成的圖，且2K1+(P3+K5)，2K1+(K2+(K5?P2))與3K1+(K5?P3)不為其子圖，矛盾。

(9)若 H=K4∨4K1,則 Hc=4K1+K4,且，由 引 理 2得，則，這樣Hc=Gc,即G=H=K4∨4K1或Hc是Gc的真生成子圖，即Gc是由Hc添加邊構(gòu)成的圖。

(9.1)若Gc是由Hc添加一條邊構(gòu)成的圖，則Gc=2K1+(K2+K4)或Gc=3K1+(K4?P2)。

若 Gc=2K1+(K2+K4)，則，這 樣 由 引 理 2得，此時G=K2∨ K2,4。

若 Gc=3K1+(K4?P2) ， 則， 由 引 理 2 得，矛盾。

(9.2)若Gc是由Hc添加兩條邊構(gòu)成的圖，則推論1與(9.1)知，Gc只能是由2K1+(K2+K4)添加邊構(gòu)成的圖，且3K1+(K4?P2)不為其子圖，則Gc為2K2+K4或K1+(P3+K4)。

若Gc=K1+(P3+K4)，則，由引理2得，矛盾。

(9.3)若Gc是由Hc添加3條邊或3條以上邊構(gòu)成的圖，則由推論1與(9.2)知，矛盾。

(10)若H=K3∨(K1+K1,3)，則Hc=3K1+(K4?P2)，且，由引理2得，則，矛盾。

(11)若H=K3∨ (K1,2+K2)，則Hc=3K1+((K1+K2)∨ 2K1)，且，由引理2得，則，這樣Gc=Hc，即，或Hc是Gc的真生成子圖，即Gc是由Hc添加邊構(gòu)成的圖。若Gc是由Hc添加邊構(gòu)成的圖，則由推論1知矛盾。

(12)若H=K2∨ K2,4，則Hc=2K1+(K2+K4),且，這樣由引理 2得，則，這樣，或Hc是Gc的真生成子圖，即Gc是由Hc添加邊構(gòu)成的圖。

(12.1)若Gc是由Hc添加一條邊構(gòu)成的圖，則，或，或

若 Gc=2K2+K4，則，由引理 2得則由推論1知此時G=K2,2∨4K1。

若 Gc=K1+(P3+K4)，則，由引理2得56=n(2n-9)≥，矛盾。

若 Gc=K1+(K2+(K4?P2))，則，由引理2得56=，矛盾。

若Gc=2K1+(P3?K4)，則，由引理2得56=n(2n-9)≥，矛盾。

(12.2)若Gc是由Hc添加兩條或兩條以上邊構(gòu)成的圖。由推論1與(12.1)知矛盾。

由上述討論得出定理1結(jié)論成立。