李 青,劉 莉,袁 慧

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

0 引言

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

圖G的離心距離和[5-6](Eccentric Distance Sum,EDS)是化學(xué)圖論中基于離心率的拓?fù)渲笖?shù).在連通圖G中,圖G的離心距離和ξd(G)定義為

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

1 相關(guān)引理

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

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

類(lèi)似地,對(duì)于任意的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).

于是,

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

2 主要結(jié)果

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

于是,

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

產(chǎn)生矛盾.

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

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

那么圖G是哈密爾頓的.

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

于是得到

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

產(chǎn)生矛盾.

結(jié)合n≥2k-1,有

于是得到

于是得到

3 結(jié)語(yǔ)

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