EDS指數與平衡二部圖的哈密爾頓性

李 青,劉 莉,袁 慧

(1.合肥幼兒師范高等專科學校公共教學部,安徽 合肥 230013;2.安慶師范大學數理學院,安徽 安慶 246133)

0 引言

圖G的鄰接矩陣A(G)的最大特征值μ(G)稱為圖G的譜半徑;圖G的無符號拉普拉斯矩陣Q(G)的最大特征值q(G)稱為圖G的無符號拉普拉斯譜半徑.在一個二部圖G=(X,Y;E)中,若|X|=|Y|,則稱此二部圖為平衡二部圖.對于平衡二部圖G=(X,Y;E),如果X中任一點與Y中任一點之間均能找到一條哈密爾頓路,那么該平衡二部圖稱為弱哈密爾頓-連通圖.

圖G的離心距離和[5-6](Eccentric Distance Sum,EDS)是化學圖論中基于離心率的拓撲指數.在連通圖G中,圖G的離心距離和ξd(G)定義為

LU等[7]根據圖G的離心距離和給出了一個圖是k-哈密爾頓、k-邊哈密爾頓或k-路覆蓋的充分條件.受文獻[7]的啟發(fā),本文利用平衡二部圖的度序列與邊條件,根據原圖或其擬補圖的離心距離和分別提出了一個平衡二部圖是可跡的、哈密爾頓或弱哈密爾頓-連通的充分條件.

1 相關引理

證明 設NG(x1)∶={z1,z2,…,zs}表示點x1的鄰點集,這里s=dG(x1).那么對于任意的zi∈NG(x1),dG(x1,zi)=1;對于任意的xi(2≤i≤n),dG(x1,xi)≥2;對于任意的yi∈YNG(x1),dG(x1,yi)≥3.于是有

D(x1)≥dG(x1)+2(n-1)+3(n-dG(x1))=5n-2-2dG(x1).

類似地,對于任意的i(2≤i≤n)和任意的j(1≤j≤n),都有

D(xi)≥dG(xi)+2(n-1)+3(n-dG(xi))=5n-2-2dG(xi),
D(yj)≥dG(yj)+2(n-1)+3(n-dG(yj))=5n-2-2dG(yj).

于是,

類似地,對于任意的i(2≤i≤n)和任意的j(1≤j≤n),都有

2 主要結果

當e(G)≤n(n-k-2)+(k+2)2時.由引理5可知,

于是,

e(G)≤n(n-k-1)+k(k+1)-(n-k-1)-k

產生矛盾.

e(G)≤n2-2(n-1)-1=(n-1)2,

當n≥9時,圖G也滿足e(G)>n2-3n+9.

那么圖G是哈密爾頓的.

當e(G)≤n(n-k-1)+(k+1)2時,由引理5可知,

于是得到

e(G)≤(n-k)2+nk-(n-k)-k

產生矛盾.

結合n≥2k-1,有

于是得到

于是得到

3 結語

本文利用平衡二部圖的度序列與邊條件,根據原圖或其擬補圖的離心距離和分別提出了一個平衡二部圖是可跡的、哈密爾頓或弱哈密爾頓-連通的充分條件.今后,如果遇到了類似問題便可運用相同方法研究圖的其他性質,這為研究圖的結構性質提供了一種行之有效的方法.