含Cn-1圖關于Wiener指數(shù)、Harary指數(shù)、hyper-Wiener指數(shù)的充分條件

梅培林，蔡改香

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

設G=(V,E)為n階簡單圖，其頂點集為V(G)={v1,v2,v3,…,vn}。邊集E=E(G)為V的二元重集構成的集合，稱E中元素{u,v}(u≠v)為G的邊，邊{u,v}記為uv。圖G頂點v的度記為d G(v)，指G中與v關聯(lián)的邊數(shù)，若每個頂點的度為n-1，則稱圖G為完全圖，記作Kn，G的最小度記作δ。G中vi到vj的最短路的長度定義為vi與vj之間的距離，記為d G(vi,vj)。如果圖G=(V,E)的頂點集V可以被劃分為互不相交的子集X和Y，使得V=X?Y且任意邊e={ }u,v滿足u∈X，v∈Y或u∈Y，v∈X，則稱G為二部圖，記作G=(X,Y;E)。若 ||X= ||Y，則稱G為平衡二部圖，若 ||X=p，||Y=q，則稱G為完全二部圖，記作Kp,q。定義Λ為2個孤立點分別與Kn-2中的兩個頂點相連所構成的圖。如果圖G的一條路（一個圈）經(jīng)過所有的頂點，那么稱之為哈密頓路（哈密頓圈）。如果G有哈密頓路（哈密頓圈），則稱G是可跡圖（哈密頓圖）。若任意2個頂點都能由一條哈密頓路相連，則稱G是哈密頓連通的。一個圈經(jīng)過的頂點數(shù)，就是該圈的長度。

連通圖G的Wiener指數(shù)是與分子化合物的物理性質(zhì)、化學性質(zhì)相關性很高的拓撲指數(shù)[1]，定義為

圖G的hyper-Wiener指數(shù)是Wiener指數(shù)的推廣[2]，Klein等將hyper-Wiener指數(shù)的定義延伸到了所有的連通圖中[3]。圖G的hyper-Wiener指數(shù)定義為

圖G的Harary指數(shù)是化學圖論中非常重要的拓撲指數(shù)，由Plavchecksic和Ivanciuc等在1993年提出[4-5]，連通圖G的Harary指數(shù)定義為

拓撲指數(shù)在圖論中有很多應用，任麗芳等在文獻[6]中給出了Wiener指數(shù)、Harary指數(shù)與哈密頓性的一些結論，胡啟明等在文獻[7]中利用Wiener指數(shù)、Harary指數(shù)和hyper-Wiener指數(shù)給出了泛圈圖的一些充分條件?？紤]到拓撲指數(shù)在圈長中也有應用，受文獻[8]啟發(fā)，本文利用Wiener指數(shù)、hyper-Wiener指數(shù)和Harary指數(shù)給出圖包含一個Cn-1的充分條件。

1 相關引理

2 主要結論

的圈，除非G?K1∨(Kn-3+K2)或者G?Λ。

3 總結

通過研究文獻[8]中關于圖包含長度為n-1圈的結論，結合文獻[7]中運用拓撲指數(shù)來討論泛圈圖的性質(zhì)，本文利用Wiener指數(shù)、Harary指數(shù)和hyper-Wiener指數(shù)分別給出了n階簡單圖，n階2-連通圖包含長度為n-1的圈的充分條件。另外，圈長與圍長跟拓撲指數(shù)聯(lián)系緊密，這是我們今后研究工作的重點。