給定點數(shù)，最小度和條件直徑的圖的邊數(shù)的上界?

馬花萍，田應(yīng)智

(新疆大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，新疆 烏魯木齊 830046)

0 引言

本文中沒有定義的圖論術(shù)語和符號,請參考文獻(xiàn)[1],在這篇文章中主要研究的是有限簡單圖.設(shè)G 是一個頂點集為V(G),邊集為E(G)的圖,圖G 的階n=|V(G)|為其頂點的數(shù)目,m=|V(G)|為其邊的數(shù)目.對于V(G)中的每一個點v ∈V(G),NG(v)表示與點v 相鄰的所有的頂點的集合,用NG(v)表示v 的鄰點集,并且dG(v)=|NG(v)|稱為圖G 中點v 的度數(shù).用δ(G)表示圖G 的最小度.對于兩個不交的點子集V1和V2,[V1,V2]G表示圖G中所有邊的集合,連接了點集V1和V2中的點.取任意數(shù)x,其中x表示x 取上整數(shù),即為不小于x的最小整數(shù),x表示x 取下整數(shù),即為不超過x 的最大整數(shù).

任意兩個點u 和v 之間的距離dG(u,v)定義為圖G 中從點u 到v 的最短路的長度.對于連通圖G,定義其直徑D(G)為max{dG(u,v):u,v ∈V(G)},如果圖G 不連通,則D(G)=∞.設(shè)V1?V(G)和V2?V(G) 是V(G)的兩個非空點子集,用d(V1,V2)表示u ∈V1和v ∈V2之間的最短距離dG(u,v).為減少歧義,本文用N(v),d(v),[V1,V2],d(u,v)和d(V1,V2)表示NG(v),dG(v),[V1,V2]G,dG(u,v)和dG(V1,V2).

Balbuena等人在文獻(xiàn)[2]中推廣了直徑,介紹了圖G 的條件直徑,給定條件P 使得V(G)中至少有一對非空點子集(V1,V2)滿足給定的條件P,條件直徑DP(G)定義為max{dG(V1,V2):?/=V1,V2?V(G),其中(V1,V2) 滿足條件P}.由于條件直徑是測量具有給定條件的頂點子集之間的最大距離,因此它們可以用于某些需要控制特定網(wǎng)絡(luò)群集之間的通信延遲.

設(shè)l 和s 是兩個整數(shù)且滿足1 ≤s ≤l.考慮P 滿足下面條件:(Vl,Vs)?V(G)×V(G)滿足P 當(dāng)且僅當(dāng)|Vl|=l和|Vs|=s.在這種情況下,文獻(xiàn)[3]中用D(G;l,s)來表示條件直徑DP(G),即

注意到D(G;1,1)恰好為圖的直徑D(G),并且當(dāng)D(G;l,s)=0 時當(dāng)且僅當(dāng)l+s>|V(G)|.同時當(dāng)l+s ≤|V(G)|時有D(G;l,s)≤|V(G)|+1?(l+s).

給定點數(shù),最大度和直徑條件下圖的邊數(shù)下界是由Erd?os和R′enyi在文獻(xiàn)[4]以及Erd?os,R′enyi和S′os在文獻(xiàn)[5]中給出的.給定點數(shù),最小度和直徑條件下圖的邊數(shù)下界由Bollob′as在文獻(xiàn)[6]中給出的.由于圖G 添加一條邊其條件直徑D(G;l,s)不會增加,因此很自然的就會問給定點數(shù)和條件直徑下圖的邊數(shù)上界.當(dāng)l=s=1 時,Ore在文獻(xiàn)[7]中得到下面的結(jié)果.

定理 1[7]設(shè)G 是一個點數(shù)為n,邊數(shù)為m 和直徑為d 的連通圖.則

同時這個界是最優(yōu)的.

如果給定最小度,Mukwembi在文獻(xiàn)[8]中得到下面的結(jié)果.

定理 2[8]設(shè)G 是一個點數(shù)為n,邊數(shù)為m,直徑為d 和最小度為δ(G)=δ ≥2 的連通圖.則

同時對于給定的δ 這個界是漸進(jìn)緊的.

在文獻(xiàn)[9]中,Ali等人給出對任意無三角形圖限制其點數(shù)，直徑和邊連通度的邊數(shù)的界.Balbuena等人在[3]中給出給定點數(shù)和條件直徑的圖的邊數(shù)上界,這個結(jié)果推廣了定理1.

定理 3[3]令l 和s 為整數(shù)且1 ≤s ≤l.設(shè)圖G 是一個點數(shù)為n,邊數(shù)為m,條件直徑為D(G;l,s)=d 的連通圖.則

并且這些界是最優(yōu)的.

根據(jù)以上結(jié)果本文給出了給定點數(shù)，最小度和條件直徑下圖的邊數(shù)上界,本文推廣了文獻(xiàn)[8]的結(jié)果.

1 主要結(jié)果

在本節(jié)中,假設(shè)n,l,s 和d 是四個給定的整數(shù),使得1 ≤s ≤l 和1 ≤d ≤n+1?(l+s).

設(shè)圖G 的點數(shù)為n,邊數(shù)為m，條件直徑為D(G;l,s)=d.由條件直徑的定義可知,存在兩個子集L,S ?V(G)其中|L|=l 且|S|=s,使得d(L,S)=d.當(dāng)d=1 時m其中等式成立當(dāng)且僅當(dāng)G 同構(gòu)于完全圖Kn.當(dāng)d=2 時n ≥l+s+1,G 的條件直徑d(L,S)=2,即存在兩條邊wu 和wv，其中u ∈L,v ∈S 和w ∈V(G)(L∪S),并且在L 和S 之間沒有邊,即沒有一條邊的一個點在L 中,另一個點在S 中,因此其中等式成立當(dāng)且僅當(dāng)G 同構(gòu)于完全圖Kn刪除基數(shù)為l 和s 的兩個不相交的點子集之間的所有邊.因此下面討論d ≥3的情況.

對任意的u,v ∈A1有d(u,v)≥3.故

其中j=1,2,···,δ.對任意的yi,yj∈A3有d(yi,yj)≥6,則

其中j=1,2,···,δ.

對式(1)和(2)求和得

對式(1)和(3)求和得

由式(4)和(5)式可得

其中j=1,2,···,δ.對任意的yi,yj∈A3有d(yi,yj)≥6,則

其中j=1,2,···,δ.

對式(1)和(6)求和得

對式(1)和(7)求和得

同樣地,由式(8)和(9)可得

斷言1 已證.

因為L′中的每一個點都在A∪L′中至多有l(wèi)?1 個鄰點,S′中的每一個點都在A∪S′中至多有s?1 個鄰點,且由于d(L,S)=d ≥3,則R 中不存在一個點的鄰點既在L′中也在S′中,故

這就證明了定理4(iii).定理4 證畢.

注意到D(G;1,1)=D(G),定理4 與定理2 相同.即當(dāng)l=s=1 時,定理4(iii)的上界恰好等于定理2 的上界.

下面證明在給定點數(shù),最小度和條件直徑下構(gòu)造圖證明定理4 的上界是漸進(jìn)緊的.這里只討論定理4(i)的情形,(ii) 和(iii)的情況與(i)的類似,就不在重復(fù)說明.

設(shè)d ≥3 為整數(shù),且d ≡0 (mod 3).令n,δ,l 和s 為整數(shù),使得δ ≥2,δ+1 ≤s ≤l 和d ≤n+1?(l+s).構(gòu)造點集劃分為V(G)=V0∪V1∪···Vd的圖G 如下:

對任意兩個不同的點u,v ∈V(G),設(shè)u ∈Vi和v ∈Vj,如果在圖G 中u 和v 有邊當(dāng)且僅當(dāng)|i ?j|≤1,則|V(G)|=n,δ(G)=δ,D(G;l,s)=d 和

即對給定的最小度定理4(i)的上界是漸進(jìn)緊的.