Wiener指數(shù)，hyper-Wiener指數(shù)與圖的哈密爾頓-連通性

舒阿秀，王禮想，于濤

(安慶師范大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(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}簡(jiǎn)記為uv。記為G的補(bǔ)圖，其頂點(diǎn)集V()=V(G)，邊集E()為把G中所有不相鄰頂點(diǎn)對(duì)連接起來得到的邊的集合。頂點(diǎn)v的度dG(v)是指G中與v關(guān)聯(lián)的邊數(shù)，G的最小度記為δ(G)。G中vi到vj的最短路的長(zhǎng)度，定義為vi與vj之間的距離，記作dG(vi,vj)。如果圖G的每個(gè)頂點(diǎn)的度均為n-1，則稱G為完全圖，記作Kn。如果圖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)。若|X|=p，|Y|=q，并且X中所有頂點(diǎn)與Y中所有頂點(diǎn)都相鄰，則稱G=(X,Y;E)為完全二部圖，記作Kp,q。 設(shè)G1=(V1,E1)與G2=(V2,E2)是兩個(gè)頂點(diǎn)不交的簡(jiǎn)單圖，它們的并圖為G1∪G2=(V1∪V2,E1∪E2)，又記為G1+G2。若G1=…=Gk，我們用kG1來表示G1∪ …∪Gk。它們的聯(lián)圖為G1∨G2=((G1)c∪(G2)c)c，即 在G1∪G2中添加由G1中每個(gè)頂點(diǎn)到G2中每個(gè)頂點(diǎn)的邊所得的圖。一條包含圖G中所有頂點(diǎn)的路稱為哈密爾頓路。如果圖G中任意兩頂點(diǎn)都一條哈密爾頓路相連，則稱G是哈密爾頓-連通的。記clk(G)為G的閉包，它是指用下述方法從G中得到的一個(gè)圖:反復(fù)連接G中度之和不小于k的不相鄰的頂點(diǎn)對(duì)，直到?jīng)]有這樣的頂點(diǎn)對(duì)存在為止。

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

即:

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

決定一個(gè)給定的圖是否是哈密爾頓的，是圖論中的一類NP問題。近年來，隨著研究的不斷深入，學(xué)者們利用拓?fù)渲笖?shù)刻畫圖的哈密爾頓性，有了很大的突破，得到了很多充分或必要條件。在最小度δ≥k時(shí)，華洪波和寧博在[4]中利用圖的Wiener指數(shù)，給出了一般連通圖是哈密頓的和可跡的充分條件。蔡改香，余桂東等在[5]中利用圖的hyper-Wiener指數(shù)給出一般連通圖可跡的和哈密爾頓的充分條件。劉瑞芳等在[6]和[7]中，首先利用補(bǔ)圖的Wiener指數(shù)，Harary指數(shù)給出一般圖是可跡的和哈密爾頓的充分條件。我們根據(jù)以上文章得到啟發(fā)，在[8]的相關(guān)條件的基礎(chǔ)上，利用圖及其補(bǔ)圖的Wiener指數(shù)、hyper-Wiener指數(shù)，給出了具有最小度條件的連通圖是哈密爾頓-連通的幾個(gè)充分條件。

1 相關(guān)引理

引理1.1[8]設(shè)G為n階連通圖，n≥6k2-8k+5，δ≥k≥2，如果

則G是哈密爾頓-連通的，除非

2 主要結(jié)論

定理2.1設(shè)G為n階連通圖，n≥6k2-8k+5，δ≥k≥2，如果

則G是哈密爾頓-連通的，除非

證明 假設(shè)G不是哈密爾頓-連通的，通過引理 1.1，得

這與定理?xiàng)l件

若cln+1(G)=K2∨(Kn-k-1∪Kk-1)，則通過直接計(jì)算得

這與定理?xiàng)l件

故假設(shè)不成立，即G是哈密爾頓-連通的。

定理得證。

定理2.2 設(shè)G為n階連通圖，為n階連通圖，n≥6k2-8k+5，δ≥k≥2，如果

則G是哈密爾頓-連通的。

證明 假設(shè)G不是哈密爾頓-連通的，通過引理 1.1，得

這與定理?xiàng)l件

若cln+1(G)=K2∨(Kn-k-1∪Kk-1)

或cln+1(G)=Kk∨ (Kn-2k+1∪k-1)，則其補(bǔ)圖不是連通圖，與已知條件矛盾。

故假設(shè)不成立，即G是哈密爾頓-連通的。

定理得證。

定理2.3 設(shè)G為n階連通圖，n≥6k2-8k+5，δ≥k≥2，如果

則G是哈密爾頓-連通的，除非

證明 假設(shè)G不是哈密頓-連通的，通過引理1.1，得

這與定理?xiàng)l件

若cln+1(G)=K2∨(Kn-k-1∪Kk-1)或，由引理 1.1 知，G不是哈密爾頓—連通的。

定理得證。

定理2.4 設(shè)G為n階連通圖，為n階連通圖，n≥6k2-8k+5，δ≥k≥2，如果

則G是哈密爾頓-連通的。

證明 假設(shè)G不是哈密頓-連通的，通過引理1.1，得

這與定理?xiàng)l件

若cln+1(G)=K2∨(Kn-k-1∪Kk-1)或，則其補(bǔ)圖不是連通圖，與已知條件矛盾。

故假設(shè)不成立，即G是哈密爾頓-連通的。

定理得證。