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

摘要

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

关键词

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