連通圖平均距離的界

郝國亮, 謝智紅, 張家驥

(東華理工大學(xué) 理學(xué)院, 江西 南昌 330013)

在分析傳輸網(wǎng)絡(luò)的性能與效率時, 有兩個特別受關(guān)注的因素, 即最大傳輸時延與平均傳輸時延, 在圖論中它們常被近似地抽象為兩個圖參數(shù), 即直徑與平均距離。 這兩個圖參數(shù)在結(jié)構(gòu)化學(xué)、建筑學(xué)、通訊網(wǎng)絡(luò)等領(lǐng)域有著重要的應(yīng)用。設(shè)G=(V(G)，E(G))是一個無向簡單圖, 其中V(G)為頂點集,E(G)為邊集。對G的頂點u和v, 若存在一條u-v路, 則稱u和v是連通的。 若G中的任意一對頂點都是連通的, 則稱G為連通圖。G中最短u-v路的長稱為u和v的距離, 記為d(u,v)=dG(u,v)。對于u∈V(G), 頂點u的離徑定義為ecc(u)=eccG(u)=max{d(u,x)∶x∈V(G)}。最小離徑稱為半徑, 記為r(G)；最大離徑稱為直徑, 記為d(G)。若刪掉連通圖G中頂點μ所得圖是非連通圖,則稱μ是G的割點。不含割點的連通圖稱為塊。 用deg(u)表示頂點u在圖G中的度。

圖G的σ(u)指標(biāo)定義為

σ(u)=σG(u)=∑x∈V(G)d(u,x)

記n階連通圖G中任兩點間(無序?qū)?距離和與平均距離分別為

在關(guān)于圖的距離和平均距離研究方面, Chung(1998)建立了平均距離與獨立數(shù)之間的相互關(guān)系。 周濤等(2004)利用構(gòu)造分析方法給出了Ore 定理的一個簡單證明。 盧永紅等(2013)得到了兩類特殊樹的平均距離的精確值。相關(guān)研究還可以參閱盧永紅等(2010)、Dankelmann(2000)、Doyle(1977)、Dankelman等(2004)、Plesnik(1984)文獻(xiàn)。

本文主要利用圖G的σ(u)指標(biāo)得到了與頂點數(shù)、邊數(shù)、直徑和半徑相關(guān)的連通圖的平均距離的上下界。

1 平均距離的上界

引理1 若G是頂點數(shù)為n的連通圖,則對任意頂點u∈V(G)，

(1+2+…+k)+(n-k-1)k=

f(k)≤f(d(G))=

證畢。

由引理1可得圖的平均距離的上界:

定理1 若G是頂點數(shù)為n的連通圖,則

證明 由引理1可得

證畢。

2 平均距離的下界

引理2 若G是頂點數(shù)為n的連通圖,則對任意頂點u∈V(G)，

證明 對任意頂點u∈V(G),設(shè)ecc(u)=k且P=uu1u2…uk是G的一條路使得d(u,uk)=k。則G中剩余頂點不妨記為uk+1,uk+2,…,un-1。注意d(u,ui)=i(1≤i≤k)且d(u,ui)≥1(k+1≤i≤n-1)，因此

(1+2+…+k)+(n-k-1)=

證畢。

由引理2可得如下結(jié)論:

定理2 若G是頂點數(shù)為n的連通圖,則

證明 由引理2可得

證畢。

引理3 設(shè)G是頂點數(shù)為n的塊且r(G)≥2，則對任意頂點u∈V(G)，

σ(u)≥2(n-1)-deg(u)+(r(G)-2)2

證明 對任意頂點u∈V(G),設(shè)ecc(u)=k,并設(shè)i為圖G中與u的距離為i的頂點數(shù)(i=1,2,…,k)。 由于G是塊, 所以1≥2(i=1,2,…,k-1)且k≥1。 因此, 要使

σ(u)=1·1+2·2+…+k·k

n-1-deg(u)-2(k-3)-1=

n-deg(u)-2k+4。

于是

σ(u)=1·1+2·2+(3·3+4·4+

…+(k-1)·k-1)+k·k≥

deg(u)+2(n-deg(u)-2k+4)+

2(3+4+…+(k-1))+k·1=

2(n-1)-deg(u)+(k-2)2≥

2(n-1)-deg(u)+(r(G)-2)2

證畢。

定理3 若G是頂點數(shù)為n，邊數(shù)為m的塊且r(G)≥2，則

證明 由引理3及握手定理可得

證畢。

盧永紅,康淑瑰,孟獻(xiàn)青. 2013. 兩類特殊樹的距離和及平均距離[J]. 中北大學(xué)學(xué)報:自然科學(xué)版, 34(5): 496-499.

盧永紅,劉宏英. 2010. 幾類樹的距離和及平均距離[J].山西師范大學(xué)學(xué)報:自然科學(xué)版,24(2):16-19.

周濤,徐俊明,劉雋. 2004. 圖直徑與平均距離的極值問題研究[J].中國科學(xué)技術(shù)大學(xué)學(xué)報, 34(4):410-413.

Chung F R K. 1988. The average distance and the independence number[J]. Journal of Graph theory, 12: 229-235.

Dankelmann P. 2000. Entringer R. Average distance, minimum degree, and spanning trees[J]. Journal of Graph Theory, 33(1):1-13.

Dankelmann P, Oellermann O R, Wu J L. 2004. Minimum average distance of strong orientations of graphs[J]. Discrete Applied Mathematics,143:204-212.

Doyle J K. 1977. Mean distance in a graph[J]. Discrete Math., 17:147-154.

Plesnik J. 1984. On the sum of all distances in a graph or digraph[J]. J. Graph Theory, 8:1-21.