分裂圖的Wiener指標(biāo)

李亞平，唐子興

(喀什大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，84400，新疆，喀什)

0 引言

本文所考慮的圖都是連通的、簡單的、有限圖。設(shè)G=(V,E)是頂點(diǎn)集為V，邊集為E的有限簡單圖，用v(G)和e(G)分別記圖G中的頂點(diǎn)數(shù)和邊數(shù)。設(shè)Kn記為n個頂點(diǎn)的完全圖。對u,v∈v(G)，頂點(diǎn)u和v之間的距離dG(u,v)是這2個點(diǎn)之間最短路的長度。圖的直徑是G中所有點(diǎn)對之間距離的最大值，也就是max{d(u,v|u,v∈v(G))}。

Wiener指標(biāo)由Wiener于1947年提出[1]，最初用來預(yù)測石蠟的沸點(diǎn)，但在理論和實(shí)踐方面都得到了廣泛的研究，文獻(xiàn)[2-5]并且也從純粹的圖論觀點(diǎn)做了研究，連通圖G的Wiener指標(biāo)是一個圖不變量，即在圖的所有可能同構(gòu)下所保留的性質(zhì)。定義為G中所有無序?qū)旤c(diǎn)之間的距離之和：

關(guān)于Wiener指標(biāo)大量的研究是在文獻(xiàn)[6-9,10-12]中積累起來的，這里僅舉幾個最近的例子。

圖G的一個團(tuán)是G的一個完全子圖；圖的獨(dú)立集是不相鄰的頂點(diǎn)組成的集合。分裂圖是它的頂點(diǎn)能劃分成一個團(tuán)C和一個獨(dú)立集I(可能為空)。設(shè)G=(C∪I,E)是分裂圖，這里C={u1,u2,…，uk}是團(tuán)，I={v1,v2,…,vn-k}是獨(dú)立集，C的頂點(diǎn)與I的頂點(diǎn)之間沒有邊的限制，它們之間可以任意連邊。分裂圖在過去的幾年里得到了廣泛的研究[13-15]。眾所周知，對于n個頂點(diǎn)的任何連通圖G都有結(jié)果：

很明顯，Kn是一個分裂圖，因此很容易得出Kn是n階的所有分裂圖中Wiener指標(biāo)最小的圖。

1 主要結(jié)果

1.1 連通分裂圖

由文獻(xiàn)[16]中得到的靈感，在這一節(jié)給出了分裂圖的結(jié)構(gòu)使其具有最大的Wiener指標(biāo)，其中結(jié)構(gòu)的意思是，分裂圖G=(C∪I,E)中團(tuán)的頂點(diǎn)個數(shù)以及獨(dú)立集I的頂點(diǎn)如何連接到團(tuán)。從上面的描述中，很容易看到，當(dāng)k

證明：設(shè)W(G,I)是分裂圖G的Wiener指標(biāo)，這里I是一個k-部圖，每個部分的大小分別為x1,x2,…,xk；如果這些部分的大小不相等也不幾乎相等，則存在xs-xt>1；考慮如下的一個k-部圖I′，它的k部分的頂點(diǎn)數(shù)分別為x1,x2,…,xs-1,…,xt+1,…,xk，則

因此

W(G,I′)-W(G,I)=xs-xt-1≥xt+2-xt-1=1。

證畢。

由上面得到I中的點(diǎn)對之間dI(vi,vj)=3當(dāng)且僅當(dāng)vi和vj在不同的部。提出一個概念，n個頂點(diǎn)的簡單完全k部圖，其中所有部的大小盡可能相等，稱為Turán圖，記為Tk,n。結(jié)合上面的結(jié)果，有以下。

定理1：設(shè)連通的分裂圖G是由k個點(diǎn)的團(tuán)C和所有部的大小盡可能相等的k-部構(gòu)成的，這里每個部的點(diǎn)共同連接在團(tuán)C的一個頂點(diǎn)上，不同部的頂點(diǎn)不能連在同一個點(diǎn)上，則

證明：設(shè)圖G的k個部分的大小分別為x1,x2,…,xk，則

由以上結(jié)果能得到直徑為3、階數(shù)為n的分裂圖，團(tuán)的頂點(diǎn)數(shù)為多少時，有最大的Wiener指標(biāo)。很明顯，從Wiener指標(biāo)的定義可以看出，對所有圖G有

這里diam(G)是圖G的直徑。

1.2 2-連通分裂圖

觀察1：設(shè)G=(C∪I,E)是一個2-連通的分裂圖，如果G有最大的Wiener指標(biāo)，則團(tuán)C是偶的。

證明：假如C是奇的，把團(tuán)C的頂點(diǎn)移給I一個，則圖G的Wiener指標(biāo)將增加。