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

The Average Connectivity of Minimally Strong Blocks

作　　者：冯丽华 田应智[1] FENG Lihua;TIAN Yingzhi(School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830017,China)

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐830017

出　　处：《新疆大学学报（自然科学版）（中英文）》2023年第1期36-42,共7页Journal of Xinjiang University(Natural Science Edition in Chinese and English)

基　　金：国家自然科学基金“点(边)-k-极大r-一致超图的边数研究”(12261086).

摘　　要：令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.

关 键 词：强连通块 极小强连通块 平均连通度 

分 类 号：O157.5[理学—数学]