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

Abstract: 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.

Key words: digraph, connectivity, maximally connected, super-connected