弱哈密頓連通圖關(guān)于Wiener指數(shù)，Harary指數(shù)，hyper-Wiener指數(shù)的充分條件

梅培林，蔡改香

（安慶師范大學(xué)數(shù)理學(xué)院，安徽安慶246133）

設(shè)G=(V ,E)為n階簡(jiǎn)單圖，其頂點(diǎn)集V =V(G)={v1,v2,…,vn}，邊集E=E(G)為V的二元重集構(gòu)成的集合。稱 E 中元素{u,v}(u ≠v)為 G 的邊，邊{u,v}記為 uv。頂點(diǎn) v 的度 dG(v)是指 G 中與 v 關(guān)聯(lián)的邊數(shù)，G的最小度記作δ。G中vi到vj的最短路的長(zhǎng)度，定義為vi與vj之間的距離。如果圖G=(V ,E)的頂點(diǎn)集V可以被劃分為互不相交的子集X和Y，使得V =X ?Y且任意邊e={ u,v }均滿足u∈X，v∈Y或u∈Y，v∈X，則稱G為二部圖，可記作G=(X ,Y;E)。定義是完全圖Kn,n通過(guò)刪除它子圖Kt-1,n-t的所有邊得到的圖，其中2 ≤t ≤(n +1)/2。如果任意兩個(gè)不同部分的頂點(diǎn)可以通過(guò)哈密頓路連接，那么該二部圖為弱哈密頓連通圖。如果圖G的一條路或一個(gè)圈經(jīng)過(guò)所有的頂點(diǎn)，那么稱之為哈密頓路和哈密頓圈。如果G有哈密頓路或者哈密頓圈，則稱G是可跡圖或者哈密頓圖。如果任意兩個(gè)頂點(diǎn)都能由一條哈密頓路相連，則稱G是哈密頓連通的。

連通圖G的Wiener指數(shù)，是與分子化合物的物理性質(zhì)、化學(xué)性質(zhì)相關(guān)性很高的拓?fù)渲笖?shù)，是1947年由Wiener[1]首先提出的，記為W(G)，被定義為G的任意兩點(diǎn)的距離之和，即。

圖G 的hyper-Wiener指數(shù)作為 Wiener指數(shù)的推廣，記為 WW(G)，是1993 年Randi?[2]首先提出的，并同時(shí)給出了無(wú)圈圖hyper-Wiener的定義，進(jìn)一步，1995年Klein等[3]將hyper-Wiener的定義延伸到了所有的連通圖中。圖G的hyper-Wiener指數(shù)被定義為

圖G 的Harary 指數(shù)是化學(xué)圖論中一個(gè)非常有用的拓?fù)渲笖?shù)，記為H(G)，是1993 年由Plavchecksic等[4]和Ivanciuc等[5]首先提出的。連通圖G的Harary指數(shù)被定義為

最近，拓?fù)渲笖?shù)在很多方面都有運(yùn)用，文獻(xiàn)[6]給出了Wiener指數(shù)、Harary指數(shù)關(guān)于哈密頓圖的一些充分條件；然后文獻(xiàn)[7]進(jìn)一步給出了Wiener指數(shù)、Harary指數(shù)、hype-Wiener指數(shù)關(guān)于圖的哈密頓性的一些充分條件。但是弱哈密頓連通圖的相關(guān)拓?fù)渲笖?shù)，還沒(méi)人進(jìn)行研究，本文利用Wiener指數(shù)、hyper-Wiener指數(shù)和Harary指數(shù)給出弱哈密頓連通圖的一些充分條件。

1 相關(guān)引理

引理1設(shè)G是連通的平衡二部圖則

證明（1）設(shè)則

等號(hào)成立當(dāng)且僅當(dāng)如果x,y屬于不同部分，d(x,y)≤3；x,y屬于同一部分，d(x,y)=2，即引理得證。

（2）設(shè)G=[ X ,Y ]，X={ x1,x2,…,xn},Y ={ y1,y2,…,yn}，則

等號(hào)成立當(dāng)且僅當(dāng)如果x,y屬于不同部分，d(x,y)≤3，x,y屬于同一部分，d(x,y)=2，即引理得證。

引理2 設(shè)G是連通的平衡二部圖，|X |= |Y |=n，WW(G)≥9n2-3n-5e(G)，對(duì)于圖G中任意兩個(gè)點(diǎn)x,y，如果x,y屬于不同部分，等號(hào)成立當(dāng)且僅當(dāng)d(x,y)≤3；如果x,y屬于同一部分，等號(hào)成立當(dāng)且僅當(dāng)d(x,y)=2。

證明設(shè)G=[X,Y]，X={x1,x2,…,xn},Y={y1,y2,…,yn}，則

等號(hào)成立當(dāng)且僅當(dāng)如果x,y屬于不同部分，d(x,y)≤3；x,y屬于同一部分，那么d(x,y)=2。

引理3[8]設(shè)G(X,Y,E)是一個(gè)平衡二部圖，|X|= |Y|=n。如果δ(G)≥k≥1，n≥2k，e(G)＞n(n-k)+k(k+1)，則G是弱哈密頓連通的。

2 主要結(jié)論

定理1設(shè)G(X,Y,E)是一個(gè)連通的平衡二部圖，|X|= |Y|=n，δ(G)≥k≥2。如果n≥2k+1，，則G是弱哈密頓連通的。

證明通過(guò)引理1 可得則

定理2設(shè)G(X,Y,E)是一個(gè)連通的平衡二部圖如果n≥2k+1，，則G是弱哈密頓連通圖。

證明通過(guò)引理1 可得如果則

定理3設(shè)G(X,Y,E)是一個(gè)連通的平衡二部圖，|X|= |Y|=n，δ(G)≥k≥2。如果n≥2k+1，則G是弱哈密頓連通圖。

證明通過(guò)引理2 可得，則

3 總 結(jié)

通過(guò)研究文獻(xiàn)[8]中關(guān)于二部圖的弱哈密頓連通性的結(jié)論，聯(lián)想到文獻(xiàn)[7]中運(yùn)用拓?fù)渲笖?shù)來(lái)討論圖的哈密頓性。由此受到啟發(fā)，本文利用Wiener指數(shù)、Harary指數(shù)和hyper-Wiener指數(shù)分別給出了平衡二部圖是弱哈密頓連通的充分條件。另外，二部圖與泛圈圖跟拓?fù)渲笖?shù)有著緊密的聯(lián)系，這也是我今后的工作重點(diǎn)。