2P-哈密爾頓二部連通圖的能量條件

徐 弈，王禮想，舒阿秀

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

一個哈密爾頓圖，是指包含一個過所有頂點的圈的圖。如果圖G中任意兩頂點都有一條哈密爾頓路相連，則稱G是哈密爾頓-連通的。如果平衡二部圖G中不在同一分部中的任意一對頂點都有一條哈密爾頓路相連，則稱G是哈密爾頓二部連通的。若一個平衡二部圖G刪除一個階為2P的平衡子集后的子圖是哈密爾頓二部連通的，則稱G是2P-哈密爾頓二部連通的。由此可以看出，當p=0時，所表達的就是平衡二部圖的哈密爾頓二部連通性。

圖的哈密爾頓問題的研究一直是一個經典而又困難的問題，近年來研究這類問題的文獻較多，而最近提出了一種新思想，即用能量刻畫圖的一些性質，亦取得了一些成果。如李饒在文獻[1-2]中給出了用能量刻畫無向簡單圖性質的一些條件；余桂東等在文獻[3]中用帶有最大度的能量刻畫了無向簡單圖的哈密爾頓性。基于這些研究，本文用補圖的能量給出了一個平衡二部圖是2P-哈密爾頓二部連通的一個充分條件。

設G= ( )X,Y；E 是一個平衡二部圖，它的k 閉包定義為將所有度和大于等于k 的頂點對(x,y)連接起來，其中x ∈X,y ∈Y，記為clk(G)。下面先介紹一些相關引理。

引理1[4]設P ≥0，G是一個2n階平衡二部圖。G是2P-哈密爾頓二部連通的當且僅當cln+p+2(G)是2P-哈密爾頓二部連通的。

引理2[5]設e是圖G的任意一條邊，則有左邊等號成立當且僅當e是圖G的一條孤立邊，右邊等號不成立。

引理3[6]設G 是一個n 階圖，有度序列d1≤d2≤···≤dn，則λ2(G)≥等號成立當且僅當G是正則圖或者二部半正則圖。

引理4[7]設G是一個二部圖，則有λ(G)≤

定理1設G=是一個平衡二部圖，滿足=n ≥p+3。若

則G= ( X,Y；E )是2P-哈密爾頓二部連通的。

證明設G= ( X,Y；E )是一個滿足定理條件的平衡二部圖。如果G不是2P-哈密爾頓二部連通的，則由引理1，圖H =cln+p+2(G)也不是2P-哈密爾頓二部連通的，因而，H不是完全二部圖。由閉包的性質可知，H中任意一對不相連的頂點對(x,y)（其中x ∈X,y ∈Y）有dH(x)+dH(y)≤n+p+1。這意味在H的補圖H*中，任意一對相連頂點對(u,v)都有dH*(u)+dH*(v)=n-dH(u)+n-dH(v)≥n-p-1，因而得出

結合（1）式和引理4，可得

因為H*是平衡二部圖，所以λ(H*)=-λ1(H*)。由圖能量的定義和Cauchy-Schwartz不等式得

等號成立當且僅當λ2(H*)=···=λ2n-1(H*)。

令s=e(G*)-e(H*)，因為H非空，所以至少有一對相鄰頂點滿足dH(x)+dH(y)≤n+p+1，則

因 而s=e(G*)-e(H*)=e(H)-e(G)≤e(H)-(n2-e(G*))≤e(G*)-n+p+2。由 引 理2，可 以 找 到ε(H*)和ε(G*)之間的聯系，即

又因為e(H*)≤e(G*)，代入（3）式可得

等式（1）成立當且僅當G 是正則圖或者二部半正則圖，等式（4）成立e(H)=n+p+1+(n-1)2，等式（5）成立當且僅當G有s條孤立邊，相互矛盾，因而（1）、（2）、（4）、（5）式等號不能同時成立，所以（6）式等號取不到，因而

這與假設矛盾，因而定理成立。