关于有向图弧连通度的一些结果

王晓丽,张 磊

(晋中学院 数学学院，山西 榆次 030619)

0 引言

1 主要结论

引理1.2[4]设(X,Y)为有向图D的任一满足|(X,Y)|≤δ-1的弧割，则|X|≥max{δ++1,ξ++2}且|Y|≥max{δ-+1,ξ-+2}.

kp(p-1)+k(|X|-p)(p-1)+λ=k(p-1)|X|+λ

故

证明 令X,Y,D′,D″,J与定理1.4证明中的相同.

故

由|Y|≥a，故可以同样的方法在D″中定义Ci″(1≤i≤J)和Ctj″(j=1,2,…,k)

同理可证

因此有

2 结语

本文给出了有向图弧连通度与图的团数、图的度序列之间的关系，推论给出了有向图弧连通度与最小度的关系.如果能够证明这个下界是最好的下界，文章内容就更丰富了，这将是未来需要努力的方向.