Wiener指數，Hyper-Wiener指數，Harary指數與圖的β-虧損性

夏祥偉，葉淼林

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

本文所涉及的圖均為簡單無向連通圖。設G=( )V,E是n階m條邊的簡單連通圖，其頂點集為V=，邊集為E，其中的頂點v的度d()v是指G中與v關聯的邊的數目，用表示G的頂點的最小度。若在G中頂點u和v是連通的，則u和v之間的距離d( )u,v是G中最短( )u,v路的長。每一對不同的頂點都有一條邊相連的簡單圖稱為完全圖，n個頂點的完全圖記為Kn。G的補圖Gˉ是指和G有相同頂點集V的一個圖，在Gˉ中兩個頂點相鄰當且僅當它們在G中不相鄰。設和是兩個頂點不相交的圖，用表示它們的并圖；用表示它們的聯圖，即在G1?G2中添加由G1中每個頂點到G2中每個頂點的邊所得的圖。圖G的虧損數是指G中所有頂點個數與它的最大匹配中頂點個數之差，如果def( )G ≤β，則稱圖G是β-虧損的。表示

Wiener指數是在研究有機化合物的物理化學性質時經常使用的經典拓撲指數，定義為[1]

圖G的Harary指數是指該圖中所有頂點對之間的距離倒數之和[4-5]，即H記，則有H

決定一個給定的圖是否是虧損的，是圖論中的一類NP問題。近年來，各國學者對拓撲指數和圖虧損性的研究不斷深入，得到了很多充分或必要條件。Petrosyan等對圖的虧損性進行研究，得到一些有關完全圖K2n+1和def( G )界的結論[6]；文獻[7-11]通過研究部分拓撲指數討論了圖的哈密爾頓性；任麗芳等利用圖的Wiener指數、hyper-Wiener指數和Harary指數，分別給出了具有最小度條件的連通圖是哈密頓-連通的以及從任一點出發都是可跡的充分條件[12]。受上述文獻的啟發，在文獻[13]的相關條件基礎上，利用圖的Wiener指數、hyper-Wiener指數和Harary指數，給出了具有最小度條件的連通圖是β-虧損的幾個充分條件。值得注意的是，補圖的β-虧損同樣也具有一定的研究價值。下面先介紹相關引理。