Journal of University of Science and Technology of China ›› 2018, Vol. 48 ›› Issue (8): 612-617.DOI: 10.3969/j.issn.0253-2778.2018.08.002

• Original Paper • Previous Articles     Next Articles

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

  

  1. HONG Zhenmu, VOLKMANN Lutz2, XU Junming3
  • Received:2018-03-08 Revised:2018-07-11 Accepted:2018-07-11 Online:2018-08-31 Published:2018-07-11
  • Contact: XU Junming
  • About author:HONG Zhenmu, male, born in 1987, PhD/ lecturer. Research field: Combinatorics and graph theory. E-mail: zmhong@mail.ustc.edu.cn
  • Supported by:
    Supported by NNSF of China (11601002, 11571044), the University Natural Science Research Project of Anhui Province (KJ2016A003).

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

CLC Number: