极小强连通块的平均连通度

The Average Connectivity of Minimally Strong Blocks

令D=(V(D),A(D))是一个n阶有向图.如果有向图D是强连通的并且它的底图没有割点,那么称D是一个强连通块.如果D是一个强连通块,但对于任意的a 2A(D),都有D−a不是一个强连通块,那么称D是一个极小强连通块.对于任意两个点u,v∈V(D),κD(u,v)表示从u到v的局部连通度,是D中内部不交的(u,v)-有向路的最大条数.D的平均连通度定义为¯κ(D)=1 n(n−1)[∑(u,v)∈V(D)×V(D)κD(u,v)].借助度序列和耳朵分解的方法,给出了给定阶数的极小强连通块平均连通度的上界,并且猜测其严格小于3/2.

Let D=(V(D),A(D))be a digraph of order n.The digraph D is called a strong block if D is strongly connected and its underlying graph has no cut-vertex.D is called a minimally strong block,if D is a strong block,but D−a is not a strong block for every arc a of A(D).For u,v∈V(D),the local connectivityκD(u,v)from u to v is the maximum number of internally disjoint directed(u,v)-paths in D.The average connectivity of D is¯κ(D)=1 n(n−1)[∑(u,v)∈V(D)×V(D)κD(u,v)].By using the method of degree sequence and ear decomposition,this paper determine some upper bounds of average connectivity among minimally strong blocks in terms of their orders,and conjecture that it is strictly less than 3/2.