有向图是极大连通的和超连通的充分条件（英文）  

Sufficient conditions for digraphs to be maximally connected and super-connected

作　　者：洪振木[1] 福克曼.鲁茨 徐俊明[3] HONG Zhenmu;VOLKMANN Lutz;XU Junming(School of Finance,Anhui University of Finance and Economics,Bengbu 233030,China;Lehrstuhl II für Mathematik,RWTH Aachen University,Aachen 52056,Germany;School of Mathematical Sciences,University of Science and Technology of China,Hefei 230026,China)

机构地区：[1]安徽财经大学金融学院,安徽蚌埠233030 [2]亚琛工业大学数学系 [3]中国科学技术大学数学科学学院,安徽合肥230026

出　　处：《中国科学技术大学学报》2018年第8期612-617,共6页JUSTC

基　　金：Supported by NNSF of China(11601002,11571044);the University Natural Science Research Project of Anhui Province(KJ2016A003)

摘　　要：设D是顶点集为V(D)的有限简单有向图.V(D)中的顶点v的度d(v)被定义为v的出度d+(v)和入度d-(v)中的最小值.如果有向图D的最小度为δ,连通度为κ,则κ≤δ.如果κ=δ,则称有向图是极大连通的.对极大连通的有向图D的每个最小点割S,如果D-S要么是非强连通的且至少有一个平凡的强连通分支,要么是平凡的,则称D是超连通的.通过弧数给出有向图或二部有向图在最小度给定时是极大连通的或超连通的充分条件,并举例说明这些条件中的下界是紧的.Let D be a finite and simple digraph with vertex set V(D).For a vertex v∈V(D),the degree d(v)of v is defined as the minimum value of its out-degree d+(v)and its in-degree d-(v).If D is a digraph with minimum degreeδand connectivityκ,thenκ≤δ.A digraph is maximally connected ifκ=δ.A maximally connected digraph D is said to be super-connected if for every minimum vertex-cut S,the digraph D-S is either non-strongly connected with at least one trivial strong component or trivial.Here some sufficient conditions for digraphs or bipartite digraphs with given minimum degree to be maximally connected or super-connected were presented in terms of the number of arcs,and some examples were given to demonstrate that the lower bound on these conditions are sharp.

关 键 词：有向图 连通度 极大连通 超连通 

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