林 泓，林曉霞，王洪波

(集美大學(xué)理學(xué)院，福建 廈門 361021)

0 引言

本文所研究的圖均為簡(jiǎn)單連通圖。令G是一個(gè)連通圖，分別以V(G)和E(G)表示G的頂點(diǎn)集與邊集，以dG(u,v)表示G的兩個(gè)頂點(diǎn)u和v的距離。G中的兩個(gè)頂點(diǎn)的距離的最大值稱為G的直徑，記為diam(G)。若圖G的頂點(diǎn)集可劃分為兩個(gè)子集X和Y，使得G的每條邊的2個(gè)端點(diǎn)分別在X和Y中，則稱G為二部圖。連通的無(wú)圈圖稱為樹，樹中度為1的頂點(diǎn)稱為懸掛點(diǎn)。本文其他未加說(shuō)明的符號(hào)和概念參見文獻(xiàn)[1]。

本文以直徑為參數(shù)得到了樹的Wiener維數(shù)的一個(gè)緊的下界。

1 樹的Wiener維數(shù)的一個(gè)緊的下界

進(jìn)一步需要以下定義。設(shè)T是一個(gè)樹，以Cd(T)表示T中具有最小距離的頂點(diǎn)的集合[2]。

如圖1中的樹T，容易計(jì)算T的12個(gè)頂點(diǎn)的頂點(diǎn)距離分別為dT(u)=22,dT(c1)=24,dT(c2)=28,dT(v1)=40,dT(v2)=30,dT(v3)=dT(v4)=dT(v5)=dT(v6)=26,dT(v7)=34,dT(v8)=42，dT(v9)=52。故Cd(T)={u}。

而關(guān)于樹的最小距離點(diǎn)有引理1和引理2。

引理1[7](Zelinka) 一個(gè)樹T的質(zhì)心Cd(T)要么由一個(gè)頂點(diǎn)構(gòu)成，要么由兩個(gè)相鄰的頂點(diǎn)構(gòu)成。

引理2[2]設(shè)P=v1v2…vk是一樹T的一條路，其中v1∈Cd(T)，v2?Cd(T)，vk是樹T的一個(gè)懸掛點(diǎn)，則有dT(v1)

令x是一個(gè)實(shí)數(shù)，以x表示不超過(guò)x的最大整數(shù)。本文的主要結(jié)論是定理1。

定理1 設(shè)T是一個(gè)樹，則有dimW(T)≥diam(T)/2+1。

證明令diam(T)=r。可假設(shè)P=v0v1v2…vr為T的一條最長(zhǎng)路，顯然v0與vr都是T的懸掛點(diǎn)。令u∈Cd(T)。注意到樹T中任意兩頂點(diǎn)有唯一一條路相連，故可假設(shè)L1是樹T中連接u和v0的唯一一條路，而L2是T中連接u與vr的唯一一條路。顯然有{V(L1)∪V(L2)}?V(P)。否則，若有一點(diǎn)vi∈V(P)(vi≠v0,vi≠vr)且vi?{V(L1)∪V(L2)}。則T中將有一個(gè)包含vi的圈，與T是樹矛盾。這樣由引理1和引理2可知，L1與L2中至少有一條路中有r/2+1個(gè)有不同頂點(diǎn)距離的頂點(diǎn)，故dimW(T)≥diam(T)/2+1。

注1 定理1的下界為緊的。以Pn表示有n個(gè)頂點(diǎn)的路，diam(Pn)=n-1,dimW(Pn)=(n-1)/2+1，故dimW(Pn)=diam(Pn)/2+1。

注2 每個(gè)樹都是二部圖，但定理1的結(jié)論不能推廣到二部圖。以Cn表示有n個(gè)頂點(diǎn)的圈。C2n(n≥2)是二部圖，diam(C2n)=n，而dimW(C2n)=1。若一個(gè)連通圖G的任意兩個(gè)頂點(diǎn)間有且僅有唯一一條最短路相連，則稱一個(gè)圖G為測(cè)地的。測(cè)地圖(geodetic graphs)是圖的距離理論中常研究的一類圖[2]。顯然每個(gè)樹都是測(cè)地的，但定理1的結(jié)論也不能推廣到測(cè)地圖。C2n+1(n≥1)是測(cè)地圖，diam(C2n+1)=n，而dimW(C2n+1)=1。