王曉麗

(晉中學(xué)院 數(shù)理學(xué)院，山西 晉中 030619)

0 引言

一個(gè)有向圖D,V=V(D)和A=A(D)分別是有向圖D的頂點(diǎn)集和弧集.有向圖D的階是D中頂點(diǎn)的數(shù)目，常用n=|V(D)·表示，有向圖D的規(guī)模是D中弧的數(shù)目，常用m=|A(D)·表示.如果xy是D的一條弧，稱x控制y,且稱x為弧的尾，y為弧的頭.設(shè)X和Y是有向圖D的頂點(diǎn)子集，定義(X，Y)={xy∈A(D)∶x∈X，y∈Y}為D的弧子集，包含了有向圖D中全體尾在X、頭在Y中的弧.定義集合

N+(v)={u∈V(D)-v∶vu∈A(D)},N-(v)={w∈V(D)-v∶wv∈A(D)}.

分別稱集合N+(v),N-(v)為頂點(diǎn)v的出鄰集和入鄰集.定義d+(v)=|N+(v)·和d-(v)=|N-(v)·分別是頂點(diǎn)v的出度和入度.頂點(diǎn)v的度d(v)=min{d+(v)，d-(v)}.D的最小出度和最小入度分別用δ+和δ-表示，δ=min{δ+，δ-}是有向圖D的最小度.把頂點(diǎn)度的不增序列d1≥d2≥…≥dn定義為D的度序列.如果D的每一對(duì)頂點(diǎn)u，v之間都存在(u，v)路，則稱有向圖D為強(qiáng)連通的.對(duì)于強(qiáng)連通有向圖D,設(shè)S是D的弧子集，若D-S不是強(qiáng)連通的，則稱S是D的一個(gè)弧割.若有向圖D不含數(shù)目少于k條弧的弧割，稱D是k弧強(qiáng)連通的.使得D是k弧強(qiáng)連通的最大的整數(shù)k叫做D的弧連通度，記為λ(D).若D不是強(qiáng)連通的，則令λ(D)=0.由定義顯然λ(D)≤δ(D).

對(duì)整數(shù)p≥2,去掉有向圖D中弧的方向，再去掉產(chǎn)生的重邊得到一個(gè)簡(jiǎn)單圖，若這個(gè)簡(jiǎn)單圖不含p+1階的完全子圖，稱D的團(tuán)數(shù)ω(D)≤p.本文僅考慮有限無環(huán)無重弧的有向圖.本文未給出的術(shù)語和記號(hào)請(qǐng)參見文獻(xiàn)[1].

文獻(xiàn)[2]討論了有向圖頂點(diǎn)連通度的下界，本文討論依賴于團(tuán)數(shù)的有向圖與度序列有關(guān)的弧連通度的下界.

1 主要結(jié)論

定理1設(shè)D是一個(gè)團(tuán)數(shù)ω(G)≤p的n階有向圖，弧連通度為λ,最小度為δ，它的度序列為d1≥d2≥…≥dn.若λ≤δ-k(1≤k≤δ且k為整數(shù)),則

斷言 |X·，|Y·≥k+1.當(dāng)k=0時(shí)，顯然成立.當(dāng)k≥1時(shí)，假設(shè)|X·≤k.由于D-S中(X,Y)=?，對(duì)任意v∈X，有

δ≤d+(v)≤|X·-1+|S·≤k-1+λ.

整理可得λ≥δ-k+1,與已知λ≤δ-k矛盾，故|X·≤k+1.同理可證|Y·≤k+1.

故

證明 因λ<δ,故λ≤δ-1.定理1中當(dāng)k=1時(shí)，再由度序列的定義知

推論3設(shè)D是一個(gè)團(tuán)數(shù)ω(D)≤p的n階有向圖，最小度為δ，弧連通度為λ,度序列為d1≥d2≥…≥dn.若對(duì)任意的整數(shù)k(1≤k≤δ)，

證明 1)假設(shè)λ≤δ-k,由定理1知，

與假設(shè)λ≤δ-k矛盾，所以1)成立.

2)不難驗(yàn)證2)的條件是1)中當(dāng)k=1時(shí)的情況.由1)得λ≥δ,又λ≤δ,故λ=δ.