圖的Wiener指數(shù)的逆區(qū)間

胡 鵬，邵燕靈，劉 奇

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

1 背景

Wiener指數(shù)是一種基于分子距離的重要的拓?fù)渲笖?shù)，它能較好地反映化合物分子結(jié)構(gòu)和物理化學(xué)性質(zhì)之間的聯(lián)系。因此，為了人工合成所需要的具有某種性質(zhì)的化合物，人們可以通過刻畫具有一定 Wiener指數(shù)值的分子圖，進(jìn)而根據(jù)分子結(jié)構(gòu)進(jìn)行合成?；诨衔锓肿訄D的Wiener指數(shù)與其化學(xué)性質(zhì)之間的密切關(guān)系，1995年Gutman和Yeh[1]提出研究連通圖Wiener指數(shù)的最大逆區(qū)間問題。所謂n階圖的Wiener指數(shù)的最大逆區(qū)間問題是指：尋找一個長度最大的正整數(shù)區(qū)間[a,b]，使得對于該區(qū)間內(nèi)任意正整數(shù)c，均存在一個n階連通圖G使其Wiener指數(shù)為c。

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

2 相關(guān)引理

用Kn、Pn、Sn-1分別表示n階完全圖、路圖、星圖。在文獻(xiàn)[13]中定義了n階蒲公英圖D(n,b)，它是將一個星圖Sn-b的中心點(diǎn)(記為v0)與一個路圖Pb的某一個端點(diǎn)合并成一點(diǎn)得到的n階圖，其中b是一個正整數(shù)，且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 主要結(jié)論

下面定理1表明，當(dāng)n≤16時，引理5的結(jié)果可以被改進(jìn)。

下面考慮文獻(xiàn)[12]中定義的圖P(a1,…,ak)，它是在路Pk的k個頂點(diǎn)上依次分別粘貼a1,a2,…,ak個懸掛點(diǎn)得到的圖，其中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的中心點(diǎn)與路圖Pn-a-b的兩個端點(diǎn)粘貼而成，如圖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所示。顯然，當(dāng)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 設(shè)G=G(n;a,b)如圖2所示，則

證明由圖2可得：

(1)

因?yàn)?/p>

代入式(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)。

根據(jù)本節(jié)的引理與推論，得出本文的主要結(jié)論：

下面計算表明，當(dāng)n≥86時，定理2的結(jié)論改進(jìn)了引理5的結(jié)論。

[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.