圖的Wiener指數的逆區間

胡 鵬，邵燕靈，劉 奇

(中北大學 理學院， 太原 030051)

1 背景

Wiener指數是一種基于分子距離的重要的拓撲指數，它能較好地反映化合物分子結構和物理化學性質之間的聯系。因此，為了人工合成所需要的具有某種性質的化合物，人們可以通過刻畫具有一定 Wiener指數值的分子圖，進而根據分子結構進行合成。基于化合物分子圖的Wiener指數與其化學性質之間的密切關系，1995年Gutman和Yeh[1]提出研究連通圖Wiener指數的最大逆區間問題。所謂n階圖的Wiener指數的最大逆區間問題是指：尋找一個長度最大的正整數區間[a,b]，使得對于該區間內任意正整數c，均存在一個n階連通圖G使其Wiener指數為c。

本文主要研究n階簡單連通圖G的Wiener指數的最大逆區間問題，將2016年Matja? Krnc和Ristekrekovski提出的Wiener指數逆區間從蒲公英圖延伸到雙星圖。

2 相關引理

用Kn、Pn、Sn-1分別表示n階完全圖、路圖、星圖。在文獻[13]中定義了n階蒲公英圖D(n,b)，它是將一個星圖Sn-b的中心點(記為v0)與一個路圖Pb的某一個端點合并成一點得到的n階圖，其中b是一個正整數，且2≤b≤n-2。如果b=2,則D(n,b)即是星圖Sn-1。圖1是蒲公英圖D(17,8)。

圖1 蒲公英圖D(17,8)

引理4[12]Kn～Sn-1。

3 主要結論

下面定理1表明，當n≤16時，引理5的結果可以被改進。

下面考慮文獻[12]中定義的圖P(a1,…,ak)，它是在路Pk的k個頂點上依次分別粘貼a1,a2,…,ak個懸掛點得到的圖，其中k≥1，ai≥0,i=1,2,…,k。由此引出以下的n階雙星圖、三星圖及四星圖。

在P(a1,…,ak)中，若a2=…=ak-1=0，a1=a≥2，ak=b≥2，k=n-a-b，稱這樣的圖為n階雙星圖，記為G(n;a,b)。不難看出，雙星圖G(n;a,b)是分別將星圖Sa，Sb的中心點與路圖Pn-a-b的兩個端點粘貼而成，如圖2所示。

圖2 雙星圖G(n;a,b)

n階三星圖G(n;r,s,t)指在P(a1,…,ak)中，令a3=…=ak-1=0，a1=r，a2=s，ak=t，k≥3，記為三星圖G(n;r,s,t)，如圖3所示。顯然，當s=0時，三星圖退化為雙星圖，即G(n;r,0,t)=G(n;r,t)。

圖3 三星圖G(n;r,s,t)

n階四星圖G(n;p,q,r,t)是在P(a1,…,ak)中，令a3=…=ak-2=0，a1=p，a2=q，ak-1=r，ak=t，k≥4，如圖4所示。

圖4 四星圖G(n;p,q,r,t)

引理8 設G=G(n;a,b)如圖2所示，則

證明由圖2可得：

(1)

因為

代入式(1)合并整理得

證明完畢。

證明注意到W(G(n;r+1,s-1,t))-W(G(n;r,s,t))=s-1-r+n-r-s-2 =n-2r-3。

因此，G(n;p+1,q-1,r,t)～G(n;p+1,q-1,r-1,t+1)。

根據本節的引理與推論，得出本文的主要結論：

下面計算表明，當n≥86時，定理2的結論改進了引理5的結論。

[1] GUTMAN I，YEH Y N.The sum of all distances in bipartite graphs[J].Math Slovaca，1995，45:327-334.

[3] GOLDMAN D，ISTRAIL S，LANCIA G，et al.Algorithmic strategies in combinatorial chemistry[R].USA:Society for Industrial and Applied Mathematics Philadelphia，2000:275-284.

[4] WAGNER S.A Class of trees and its wiener index[J].Acta Appl Math，2006,9l(2):119-132.

[5] WANG H，YU G.All but 49 Numbers ale Wiener Indices of Trees[J].Acta Appl Math，2006，92(1):15-20.

[6] BAN Y A，BESPAMYATNIKH S，MUSTAFA N H.A conjecture on wiener indices in combinatorial chemistry[J].Algorithmica,2004，40(2):99-117.

[7] BEREGA S，WANG H.Wiener indices of balanced binary trees[J].Discrete Applied Mathematics,2007，155(4):457-467.

[8] CZABARKA é，SZéKELY L，WAGNER S.The inverse problem for certain tree parameters[J].Disc Appl Math,2009，157(15):3314-3319.

[9] LI X L，WANG L.Solutions for two conjectures on the inverse problem of the Wiener index of peptoids[J].SIAM J Disc Math,2004，17(2):210-218.

[10] WAGNER S，WANG H，YU G.Molecular graphs and the inverse Wiener index problem[J].Disc Appl Math，2009，157(7):1544-1554.

[11] FINK J，LU?AR B，KREKOVSKI R.Some remarks on inverse Wiener index problem[J].Disc Appl Math，2012,160:1851-1858.