Wiener指數(shù)，Hyper-Wiener指數(shù)，Harary指數(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)成的集合。稱(chēng)E中元素{u,v}(u≠v)為G的邊，邊{u,v}簡(jiǎn)記為uv。頂點(diǎn)v的度dG(v)是指G中與v關(guān)聯(lián)的邊數(shù)，G的最小度記為δ。G中vi到vj最短路的長(zhǎng)度，定義為vi與vj之間的距離，記作dG(vi,vj)。如果圖G的每個(gè)頂點(diǎn)的度均為n-1，則稱(chēng)G為完全圖，記作Kn。如果圖G=(V,E)的頂點(diǎn)集V可以被劃分為互不相交的子集X和Y，使得V=X?Y且任意邊e={u,v}均滿(mǎn)足u∈X,v∈Y或u∈Y,v∈X，則稱(chēng)G為二部圖，記作G=(X,Y;E)。若 ||X =p， ||Y=q，并且X中所有頂點(diǎn)與Y中所有頂點(diǎn)都相鄰，則稱(chēng)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來(lái)表示G1?…?Gk；它們的聯(lián)圖為G1∨G2=即在G1? G2中添加由G1中每個(gè)頂點(diǎn)到G2中每個(gè)頂點(diǎn)的邊所得的圖。一條包含圖G中所有頂點(diǎn)的路稱(chēng)為哈密爾頓路。如果圖G中任意兩頂點(diǎn)都由一條哈密爾頓路相連，則稱(chēng)G是哈密爾頓-連通的。如果圖G含有從任意一點(diǎn)出發(fā)的哈密頓路，則稱(chēng)G從任意一點(diǎn)出發(fā)都是可跡的。

連通圖G的Wiener指數(shù)W(G)[1]，是指G中任意兩個(gè)頂點(diǎn)的距離之和，即

圖G的hyper-Wiener指數(shù)[2-3]作為Wiener指數(shù)的推廣，記為WW(G)，

這與定理?xiàng)l件WW(G)

若G∈NP，由引理2知，G不是從任意一點(diǎn)2出發(fā)都是可跡的。

定理6 設(shè)G為n階連通圖，n≥5，δ≥2，如果H(G)≥則G是從任意一點(diǎn)出發(fā)都是可跡的，除非G∈NP2={K2∨(Kn-4+

證明 假設(shè)G不是從任意一點(diǎn)出發(fā)都是可跡的，由引理2可得

這與定理?xiàng)l件H(G)≥若G∈NP2，由引理2知，G不是從任意一點(diǎn)出發(fā)都是可跡的。

[1]WIENER H.Structural determination of paraffin boiling points[J].Journal of theAmerican Chemical Society,1947,69(1):17.

[2]RANDIC M.Novel molecular descriptor for structure-property studies[J].Chemical Physics Letters,1993,211(4-5):478-483.

[3]KLEIN D J,LUKOVITS I,GUTMAN I.On the definition of the hyper-Wiener index for cycle-containing structures[J].Journal of Chemical Information&Modeling,1995,35(1):50-52.

[4]PLAVCHECKSIC D,NIKOLIC S,TRINAJSTIC N,et al.On the Harary index for the characterization of chemical graphs[J].Math Chem,1993,12(1):235-250.

[5]IVANCIUC O,BALABAN T S,BALABAN A T.Reciprocal distance matrix,related local vertex invari-ants and topological indices[J].Math Chem,1993,12(1):309-318.

[6]ZHOU Q,WANG L.Some sufficient spectral conditions on Hamilton-connected and traceable graphs[J].Linear and MultilinearAlgebra,2017,65(2):224-234.