李星星，余桂東，任麗芳

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

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

圖G的Harary指數(shù)[4-5]是化學(xué)圖論中另一個(gè)非常有用的拓?fù)渲笖?shù)，,記，則有。

下面先介紹兩個(gè)相關(guān)引理。

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

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

下面給出本文的主要結(jié)論及證明。

若G∈NP1，由Winner指數(shù)的定義可直接計(jì)算得，與定理?xiàng)l件矛盾。

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

當(dāng)G ∈NP1時(shí)，由hyper-Winner指數(shù)的定義可直接計(jì)算出與定理?xiàng)l件矛盾。

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

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

當(dāng)G∈NP2時(shí)，由Winner指數(shù)的定義計(jì)算可得與定理?xiàng)l件矛盾。

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

當(dāng)G ∈ NP2時(shí)，通過hyper-Winner指數(shù)的定義計(jì)算可得與定理?xiàng)l件矛盾。

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

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

與定理?xiàng)l件矛盾。

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

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