譚尚旺,王東方,魏寧寧

(中國石油大學(xué)理學(xué)院,山東青島266580)

1 問題的提出

本文中討論的圖都是無環(huán)和無重邊的簡單圖，未定義的記號和術(shù)語見文獻(xiàn)[1]。令G是頂點(diǎn)集和邊集分別為V(G)和E(G)的一個(gè)連通圖。G的1度點(diǎn)稱為G的葉或懸掛點(diǎn)，關(guān)聯(lián)葉的邊稱為G的懸掛邊，兩個(gè)不同頂點(diǎn)u和v之間的距離dG(u，v)就是G中連接這兩個(gè)頂點(diǎn)的最短路的邊數(shù)。為了方便，記dG(u，u)=0。對頂點(diǎn)v∈V(G)，令W(G，v)表示v與G中所有其它頂點(diǎn)之間距離的和，degG(v)表示v在G中的度，并且NG(v)表示v在G中的所有鄰接頂點(diǎn)的集合。

連通圖G的維納指標(biāo)W(G)定義為G中所有不同頂點(diǎn)對之間距離的和，即

圖的維納指標(biāo)是基于距離的一個(gè)不變量，是與分子分支密切相關(guān)的最古老的拓?fù)渲笜?biāo)之一，是化學(xué)家維納在1947年設(shè)計(jì)和研究之后命名的[2-4]。維納指標(biāo)的許多化學(xué)應(yīng)用是用來處理非循環(huán)的有機(jī)分子，其中這些有機(jī)分子的圖是樹。目前，維納指標(biāo)已經(jīng)取得了許多結(jié)論，關(guān)于維納指標(biāo)的綜述和維納指標(biāo)的化學(xué)應(yīng)用及數(shù)學(xué)文獻(xiàn)見[5]～[10]及其引用的文獻(xiàn)。

Entringer等[11]證明了路Pn是所有n點(diǎn)樹中具有最大維納指標(biāo)的唯一圖，而星Sn是所有n點(diǎn)樹中具有最小維納指標(biāo)的唯一圖。Deng[11]確定了頂點(diǎn)數(shù)n≥9的所有化學(xué)樹中維納指標(biāo)具有第一最大值到第十七最大值的所有樹。Dong和 Guo[7]確定了所有n點(diǎn)樹中維納指標(biāo)具有第一最小值到第十五最小值的所有樹。Wang和Guo[12]確定了給定頂點(diǎn)數(shù)和直徑的所有樹中維納指標(biāo)最小的樹。Fishermann等[13]和Rada[14]分別獨(dú)立地確定了給定頂點(diǎn)數(shù)和最大度的所有樹中維納指標(biāo)最小的樹。令π=(d1，d2，…dn)是滿足d1≥d2≥…≥dn的一個(gè)非負(fù)整數(shù)序列，如果π是某個(gè)簡單連通圖的頂點(diǎn)度序列，則稱π是可圖的。Zhang等[15]提出了下述問題：對給定的一個(gè)可圖序列π，令

Γ(π)={G：G連通并且π是G的度序列}，求Γ(π)中所有圖的維納指標(biāo)的上(下)界并且刻劃達(dá)到上(下)界的所有極圖。

Zhang等[15]研究了上述問題的一個(gè)特殊類，即對給定的樹的一個(gè)度序列，刻劃了具有最小維納指標(biāo)的極圖，也確定了給定最大度、葉數(shù)或匹配數(shù)的所有樹中具有最小維納指標(biāo)的極圖。對上述問題，Zhang等[16]也研究了給定度序列的所有樹中具有最大維納指標(biāo)的極圖。Székely和Wang[17]確定了具有最大子樹個(gè)數(shù)的二元樹。

一個(gè)樹稱為毛毛蟲圖，如果從這個(gè)樹中刪去所有的葉后產(chǎn)生一個(gè)路。對一些圖類，盡管已經(jīng)發(fā)現(xiàn)了改變圖的維納指標(biāo)的一些變換和尋求具有最小或最大維納指標(biāo)極圖的一些方法[13-17]，但這些變換和方法在求給定度序列的毛毛蟲圖中具有最小維納指標(biāo)的極圖時(shí)是無效的。本文的動機(jī)來源于上述結(jié)論，尤其是文獻(xiàn)[15]提出的上述問題，本文中刻劃了給定度序列的所有毛毛蟲圖中具有最小維納指標(biāo)的極圖。

2 圖的兩個(gè)變換

給出圖的兩個(gè)變換并確定計(jì)算新圖維納指標(biāo)的公式，用來確定具有最小維納指標(biāo)的極端毛毛蟲圖。

引理1[18]令u是連通圖G的一個(gè)割點(diǎn)，G1和G2是G的兩個(gè)連通子圖。如果V(G1)∩V(G2)={u} 且G1∪G2=G，則。

引理2[5]令uv是連通圖G的一個(gè)割邊，G1和G2是G-uv中分別包含u和v的兩個(gè)分支。記，則W(G)=W(G1)+W(G2)+n1W(G2，v)+n2W(G1，u)+n1n2。

定理1令u是連通圖G的一個(gè)割點(diǎn)，G1和G2是G的兩個(gè)連通子圖并且V(G1)∩V(G2)={u}，G1∪G2=G，NG1(u)={u1，u2，…，us}。對G2中不同于u的另外一個(gè)點(diǎn)v，記G′=G-{uu1，uu2，…，uus}+{vu1，vu2，…，vus}，，則

特別地，如果W(G，u)≥W(G，v)，則W(G)＞W(wǎng)(G′)。

證明令G′1=G1-{uu1，uu2，…，uus}+{vu1，vu2，…，vus}，則

其中G′1的頂點(diǎn)v是G′的割點(diǎn)，且它對應(yīng)G1的頂點(diǎn)u。因此，得

由于dG2(u，v)=dG(u，v)，于是由式(3) 和(4) 得到式(2)。此外，由式(2)附加斷言顯然成立。定理證畢。

定理2令u、v、a、b是連通圖G的4個(gè)頂點(diǎn)且uv，ab∈E(G)，ua，vb?E(G)。記k=dG(v，a)，G′=G-{uv，ab}+{ua，vb}(圖1)。如果uv和ab都是G的割邊，則

圖1 定理2中從G到G′的圖Fig.1 Diagrams from G to G′in theorem 2

證明令G1、G2和G3是G-uv-ab中分別包含頂點(diǎn)u，v和b的3個(gè)分支，Q是G-uv中包含頂點(diǎn)v的分支。記。

取G的割邊uv和Q的割邊ab分別作為引理2中的邊uv，由引理2得

由W(G，u)的定義和G的假設(shè)得

通過交換式(9)的v和a，得

于是由式(12)和(13)得

因此，由式(11)得到式(5)。定理證畢。

3 給定度序列的毛毛蟲圖中具有最小維納指標(biāo)的圖

確定給定度序列的毛毛蟲圖中具有最小維納指標(biāo)的極圖。

令Pd=v0v1…vd是直徑為d的路。熟知，任一個(gè)直徑為d的樹T都能通過在Pd的頂點(diǎn)vi(i=2，3，…，d-1)上懸掛適當(dāng)?shù)臉銽i而得到。令C(s1，s2，…，sd-1)表示通過在Pd的頂點(diǎn)vi(i=2，3，…，d-1)上增加個(gè)懸掛邊得到的毛毛蟲圖。Wang和Guo[12]已經(jīng)證明

等式成立，當(dāng)且僅當(dāng)T?C(s1，s2，…，sd-1)。

基于上述結(jié)論，令C(π)表示度序列為π的所有毛毛蟲圖的集合，其中π=(d1，d2，…，dn)，d1≥d2≥…≥ds≥2＞ds+1=…=dn=1。容易發(fā)現(xiàn)，C(π)中的所有毛毛蟲圖都有相同的直徑d=1+s。令CM是C(π)中具有最小維納指標(biāo)的一個(gè)毛毛蟲圖。假設(shè)s≥3(否則，C(π)僅包含一個(gè)星圖或雙星圖)，且假設(shè)d1，d2，…，dn中至少有兩個(gè)是不同的(否則，n=1或2，問題是平凡的)。下面總假設(shè)PM=v0v1…vd是CM的一個(gè)最長路，研究CM的性質(zhì)和結(jié)構(gòu)。

引理3如果u和v都不是PM的葉并且W(CM，u) ≥W(CM，v)，則

證明假設(shè)degCM(u)＞degCM(v)。既然v不是PM的懸掛點(diǎn)，于是

這表明在頂點(diǎn)u處存在一個(gè)不包含在PM上的懸掛邊。令s=degCM(u)-degCM(v)，uu1，uu2，…，uus是CM中頂點(diǎn)u處不包含在PM上的s個(gè)懸掛邊。記T′=CM-{uu1，uu2，…，uus}+{vu1，vu2，…，vus}，則T′∈C(π)。由定理1得W(T′)＜W(CM)，這與CM的假設(shè)矛盾。引理證畢。

引理4如果u是PM的一個(gè)懸掛點(diǎn)并且v不是PM的懸掛點(diǎn)，則

證明假設(shè)W(CM，v)≥W(CM，u)。不妨設(shè)u=v0并且v=vi(1≤i≤d-1)。記

令T′=CM-{vivi+1，via1，via2，…，viat} +{v0vi+1，v0a1，v0a2，…，v0at}，則T′∈C(π)。由定理 1 得W(T′)＜W(CM)，這與CM的假設(shè)矛盾。引理證畢。

引理5令u、v、a、b是PM上依次從左到右的4個(gè)不同頂點(diǎn)，其中uv和ab是PM的兩個(gè)邊。記k=dCM(v，a)，則

證明假設(shè) Δ(u，v，a，b)＜0。令

這與CM的假設(shè)矛盾。引理證畢。

引理6如果存在非負(fù)整數(shù)0≤p＜q≤d，使W(CM，vp)=W(CM，vq)，則

假 設(shè)W(CM，vp+1) ≠W(CM，vq-1)，不 妨 設(shè)W(CM，vp+1)＜W(CM，vq-1)。考慮PM上的4個(gè)不同頂點(diǎn)：u=vp，v=vp+1，a=vq-1，b=vq，容易發(fā)現(xiàn) Δ(u，v，a，b)=[W(CM，v)-W(CM，a)][W(CM，a)-W(CM，v)](k+2)＜0.這與引理5的結(jié)論矛盾。因此，W(CM，vp+1)=W(CM，vq-1)。用p+1 和q-1分別代替上面的p和q，重復(fù)上述過程可得

假 設(shè)W(CM，vp-1) ≠W(CM，vq+1)，不 妨 設(shè)W(CM，vp-1)＞W(wǎng)(CM，vq+1)?？紤]PM上的4個(gè)不同頂點(diǎn)：u=vp-1，v=vp，a=vq，b=vq+1。容易發(fā)現(xiàn)

這與引理 5的結(jié)論矛盾。因此，W(CM，vp-1)=W(CM，vq+1)。用p-1和q+1分別代替上面的p和q，重復(fù)上述過程可得

假設(shè)p≠d-q，不妨設(shè)p＜d-q。由p+q＜d知，v0是PM的一個(gè)懸掛點(diǎn)，而vp+q是PM的非懸掛點(diǎn)。在式(16)中取i=p，得W(CM，v0)=W(CM，vp+q)，這與引理4的結(jié)論矛盾。因此，得到

由式(15)～(17)得到式(14)。

由式(14) 得W(CM，vi) ≥W(CM，vd-i)，于是由引理3得degCM(vi)≤degCM(vd-i)，這與假設(shè)矛盾。引理證畢。

引理7 (1)如果d=2s是一個(gè)偶數(shù)，則

(2)如果d=2s+1是一個(gè)奇數(shù)，則

證明首先證明(1)。由式(18)和引理4得

對1≤i≤s-1，根據(jù)式(19)，假設(shè)已經(jīng)知道W(CM，v0) ≥W(CM，v2s) ≥ … ≥W(CM，vi-1) ≥W(CM，v2s-i+1) ≥W(CM，vi).

下面證明W(CM，vi)≥W(CM，v2s-i)。如果W(CM，vi)＜W(CM，v2s-i)，則考慮PM的4個(gè)不同頂點(diǎn)：u=vi-1，v=vi，a=v2s-i，b=v2s-i+1。既然

z(CM，u) ≥W(CM，b)，W(CM，v)＜W(CM，a)，于是Δ(u，v，a，b)＜0，與引理5的結(jié)論矛盾。因此，W(CM，vi)≥W(CM，v2s-i)。上述結(jié)論也表明

對1≤j≤s-2，根據(jù)式(20)，假設(shè)已知

下面證明W(CM，v2s-j)≥W(CM，vj+1)。如果W(CM，v2s-j)＜W(CM，vj+1)，則考慮PM的4 個(gè)不同頂點(diǎn)：u=v2s-j+1，v=v2s-j，a=vj+1，b=vj。既然W(CM，u) ≥W(CM，b)，W(CM，v)＜W(CM，a)，于是Δ(u，v，a，b)＜0，與引理5的結(jié)論矛盾。因此，W(CM，v2s-j) ≥W(CM，vj+1)。

由上述兩方面的討論和歸納法原理，完成了(1)的證明。

(2)的證明與(1)的證明類似。

假設(shè)式(18)成立，即W(CM，v0)≥W(CM，vd)。記degCM(v)=deg(v)，則由引理3和引理7，當(dāng)d=2s時(shí)，

當(dāng)d=2s+1時(shí)，

這表明，對給定的樹的一個(gè)度序列π=(d1，d2，…，dn)，圖CM是唯一確定的。因此，得到下面的結(jié)論。

定理3對給定的樹的任一個(gè)度序列π，CM是C(π)中具有最小維納指標(biāo)的唯一圖。

圖2和圖3分別顯示了兩個(gè)具有最小維納指標(biāo)的毛毛蟲圖，其中

特別地，圖3顯示的毛毛蟲圖是對稱的。

圖2 C(π1)中具有最小維納指標(biāo)的毛毛蟲圖Fig.2 Caterpillar with the smallest Wiener index in C(π1)

圖3 C(π2)中具有最小維納指標(biāo)的毛毛蟲圖Fig.3 Caterpillar with the smallest Wiener index in C(π2)

[1] BONDY J A，MURTY U S R.Graph theory with applications[M].New York：Macmillan Press，1976.

[2] WIENER H.Structural determination of paraffin boiling points[J].J Am Chem Soc，1947，69：17-20.

[3] HOSOYA H.Topological index：a newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons[J].Bull Chem Soc Jpn，1971，44：2332-2339.

[4] TODESCHINI R，CONSONNI V.Handbook of Molecular Descriptors[M].Weinheim：Wiley-VCH Press，2000.

[5] DOBRYNIN A A，ENTRINGER R，GUTMAN I.Wiener index of trees：theory and applications[J].Acta Appl Math，2001，66：211-249.

[6] DENG H.The trees onn≥9 vertices with the first to seventeenth largest Wiener indices are chemical trees[J].MATCH Commun Math Comput Chem，2007，57：393-402.

[7] DONG H，GUO X.Ordering trees by their Wiener indices[J].MATCH Commun Math Comput Chem，2006，56：527-540.

[8] GUTMAN I，YEH Y N，LEE S L，et al.Wiener numbers of dendrimers[J].MATCH Commun Math Comput Chem，1994，30：103-115.

[9] XU K，TRINAJSTIC N.Hyper-Wiener and Harary indices of graphs with cut edges[J].Util Math，2011，84：153-163.

[10] DIUDEA M V，KATONA G，MINAILIUC O M，et al.Wiener and hyper-Wiener indices in spiro-graphs[J].Russ Chem Bull，1995，44：1601-1611.

[11] ENTRINGER R C，JACKSON D E，SYNDER D A.Distance in graphs[J].Czechoslovak Math J，1976，26：283-296.

[12] WANG S J，GUO X F.Trees with extremal Wiener indices[J].MATCH Commun Math Comput Chem，2008，60：609-622.

[13] FISHERMANN M，HOFFMANN A，RAUTENBACH D，et al.Wiener index versus maximum degree in trees[J].Disc Appl Math，2002，122：127-137.

[14] RADA J.Variation of the Wiener index under tree transformations[J].Disc Appl Math，2005，148：135-146.

[15] ZHANG X D，XIANG Q Y，XU L Q，et al.The Wiener index of trees with given degree sequences[J].MATCH Commun Math Comput Chem，2008，60：623-644.

[16] ZHANG X D，LIU Y，HAN M X.Maximum Wiener index of trees with given degree sequence[J].MATCH Commun Math Comput Chem，2010，64：661-682.

[17] SZEKELY L A，WANG H.Binary trees with the largest number of subtrees[J].Discr Appl Math，2007，155：374-385.

[18] BALAKRISHNAN R，SRIDHARAN N，VISWANATHAN Iyer K.Wiener index of graphs with more than one cutvertex[J].Appl Math Lett，2008，21：922-927.