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

2020-01-07 05:56:56王晓丽
关键词:榆次有向图下界

王晓丽,张 磊

(晋中学院 数学学院,山西 榆次 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 结语

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

猜你喜欢
榆次有向图下界
The Spirit of National Defense Is in Our Hearts
有向图的Roman k-控制
Lower bound estimation of the maximum allowable initial error and its numerical calculation
大惊小怪说晋商——游榆次常家庄园有感
超欧拉和双有向迹的强积有向图
关于超欧拉的幂有向图
榆次地区广告设计中汉字造型的应用
人间(2015年16期)2015-12-30 03:40:43
矩阵Hadamard积的上下界序列
最大度为10的边染色临界图边数的新下界
常维码的一个构造性下界