Wiener指數(shù)，Hyper-Wiener指數(shù)，Harary指數(shù)與圖的哈密頓性

李星星，余桂東，任麗芳

（安慶師范大學數(shù)學與計算科學學院，安徽安慶246133）

連通圖G的Wiener指數(shù)W(G)[1]，是指G中任意兩個頂點的距離之和，即,若記，則有圖G的hyper-Wiener[2-3]指數(shù)作為Winner指數(shù)的推廣，記為WW(G)，

圖G的Harary指數(shù)[4-5]是化學圖論中另一個非常有用的拓撲指數(shù)，,記，則有。

下面先介紹兩個相關引理。

引理1[6]設G為n階連通圖，，如果，則G是哈密頓-連通的，除非。

引理2[6]設G為n階連通圖，如果，則G是從任一點出發(fā)都是可跡的，除非。

下面給出本文的主要結論及證明。

若G∈NP1，由Winner指數(shù)的定義可直接計算得，與定理條件矛盾。

綜上所述，假設不成立，即G是哈密頓-連通的。

當G ∈NP1時，由hyper-Winner指數(shù)的定義可直接計算出與定理條件矛盾。

綜上所述，假設不成立，即G是哈密頓-連通的。

證明 假設G不是從任意一點出發(fā)都是可跡的，通過引理2，知或。

當G∈NP2時，由Winner指數(shù)的定義計算可得與定理條件矛盾。

證明 假設G不是從任意一點出發(fā)都是可跡的，通過引理2，知或

當G ∈ NP2時，通過hyper-Winner指數(shù)的定義計算可得與定理條件矛盾。

綜上所述，假設不成立，即G是從任意一點出發(fā)都是可跡的。

證明 假設G不是從任意一點出發(fā)都是可跡的，通過引理2，知或

與定理條件矛盾。

當G∈NP2時，由Haraary指數(shù)的定義計算可得，當n≥8時，

得到G∈NC。當G∈NC時，則由引理2知，G不是從任意一點出發(fā)都是可跡的。