依赖于团数的有向图弧连通度的下界

王晓丽

(晋中学院 数理学院，山西 晋中 030619)

0 引言

一个有向图D,V=V(D)和A=A(D)分别是有向图D的顶点集和弧集.有向图D的阶是D中顶点的数目，常用n=|V(D)·表示，有向图D的规模是D中弧的数目，常用m=|A(D)·表示.如果xy是D的一条弧，称x控制y,且称x为弧的尾，y为弧的头.设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,设S是D的弧子集，若D-S不是强连通的，则称S是D的一个弧割.若有向图D不含数目少于k条弧的弧割，称D是k弧强连通的.使得D是k弧强连通的最大的整数k叫做D的弧连通度，记为λ(D).若D不是强连通的，则令λ(D)=0.由定义显然λ(D)≤δ(D).

对整数p≥2,去掉有向图D中弧的方向，再去掉产生的重边得到一个简单图，若这个简单图不含p+1阶的完全子图，称D的团数ω(D)≤p.本文仅考虑有限无环无重弧的有向图.本文未给出的术语和记号请参见文献[1].

文献[2]讨论了有向图顶点连通度的下界，本文讨论依赖于团数的有向图与度序列有关的弧连通度的下界.

1 主要结论

定理1设D是一个团数ω(G)≤p的n阶有向图，弧连通度为λ,最小度为δ，它的度序列为d1≥d2≥…≥dn.若λ≤δ-k(1≤k≤δ且k为整数),则

断言 |X·，|Y·≥k+1.当k=0时，显然成立.当k≥1时，假设|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中当k=1时，再由度序列的定义知

推论3设D是一个团数ω(D)≤p的n阶有向图，最小度为δ，弧连通度为λ,度序列为d1≥d2≥…≥dn.若对任意的整数k(1≤k≤δ)，

证明 1)假设λ≤δ-k,由定理1知，

与假设λ≤δ-k矛盾，所以1)成立.

2)不难验证2)的条件是1)中当k=1时的情况.由1)得λ≥δ,又λ≤δ,故λ=δ.