依賴于團(tuán)數(shù)的有向圖弧連通度的下界

王曉麗

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

0 引言

一個有向圖D,V=V(D)和A=A(D)分別是有向圖D的頂點集和弧集.有向圖D的階是D中頂點的數(shù)目，常用n=|V(D)·表示，有向圖D的規(guī)模是D中弧的數(shù)目，常用m=|A(D)·表示.如果xy是D的一條弧，稱x控制y,且稱x為弧的尾，y為弧的頭.設(shè)X和Y是有向圖D的頂點子集，定義(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)為頂點v的出鄰集和入鄰集.定義d+(v)=|N+(v)·和d-(v)=|N-(v)·分別是頂點v的出度和入度.頂點v的度d(v)=min{d+(v)，d-(v)}.D的最小出度和最小入度分別用δ+和δ-表示，δ=min{δ+，δ-}是有向圖D的最小度.把頂點度的不增序列d1≥d2≥…≥dn定義為D的度序列.如果D的每一對頂點u，v之間都存在(u，v)路，則稱有向圖D為強連通的.對于強連通有向圖D,設(shè)S是D的弧子集，若D-S不是強連通的，則稱S是D的一個弧割.若有向圖D不含數(shù)目少于k條弧的弧割，稱D是k弧強連通的.使得D是k弧強連通的最大的整數(shù)k叫做D的弧連通度，記為λ(D).若D不是強連通的，則令λ(D)=0.由定義顯然λ(D)≤δ(D).

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

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

1 主要結(jié)論

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

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

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

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

故

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

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

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

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

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