單圈圖(外圍)Wiener指標的計算公式

李建喜, 雷思宇

(閩南師范大學數學與統計學院,福建漳州363000)

§1 引 言

設G=(V,E)為具有n個頂點的簡單連通圖,對于任意頂點u,v∈V(G),兩點間的距離d(u,v)為u和v之間的最短路徑長度,還可記為dG(u,v).對v∈V(G),頂點v的離心率ε(v)=max{d(u,v)|u∈V(G)},圖G的直徑d(G)=max{ε(v)|v∈V(G)}.外圍頂點集P(G)指圖中滿足ε(v)=d(G)的頂點的集合.用dG(x)記為在G中頂點x到其余頂點的距離和,即.用W(G)表示圖G的Wiener指標,PW(G)表示圖G的外圍Wiener指標.對于圖G中的割邊e∈E(G),分別用n1(e),n2(e)表示G中分布在邊e兩側的頂點數目,p1(e),p2(e)分別表示G中分布在邊e兩側的外圍頂點數目;若e∈E(G)且邊e不為G的割邊時,規定分布在邊e兩側的頂點數目分別為0.用|G|表示圖G中頂點的數目.頂點數目和邊數目相同的簡單連通圖稱為單圈圖.

圖的Wiener指標是由著名的化學家Wiener在1947年首次提出的基于距離不變量的一種拓撲指標,其與圖的結構性質之間有著密切的聯系,相關結果和進展可參見文獻[1-4].圖G的Wiener指標在文獻[1]被定義為圖中所有不同頂點對間的距離之和,即

而外圍Wiener指標是Wiener指標的一部分,是2017年由K.P.Narayankar和S.B.Lokesh在文獻[5]中在Wiener指標的基礎上首次提出.其定義為圖G中所有不同外圍頂點對間的距離之和,即

文獻[6]研究了簡單連通圖的Wiener指標和外圍Wiener指標的差的上界和下界;文獻[7]主要探究了樹圖的外圍Wiener指標,得到了樹圖外圍Wiener指標的上界和下界,還有當給定外圍頂點數目和直徑時樹圖的外圍Wiener指標的上界和下界.在文獻[7]中求樹圖的外圍Wiener指標的上下界時用得更多的公式不是定義式,而是求和每條邊對Wiener指標貢獻的一個式子,一條邊對Wiener指標的……