林 泓，林曉霞，王洪波

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

0 引言

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

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

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

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

如圖1中的樹T，容易計算T的12個頂點的頂點距離分別為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)于樹的最小距離點有引理1和引理2。

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

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

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

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

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

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

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