ISSN 0253-2778

CN 34-1054/N

Open AccessOpen Access JUSTC Original Paper

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

Funds:  Supported by NNSF of China (11601002, 11571044), the University Natural Science Research Project of Anhui Province (KJ2016A003).
Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2018.08.002
More Information
  • Author Bio:

    HONG Zhenmu, male, born in 1987, PhD/ lecturer. Research field: Combinatorics and graph theory. E-mail: zmhong@mail.ustc.edu.cn

  • Corresponding author: XU Junming
  • Received Date: 08 March 2018
  • Accepted Date: 11 July 2018
  • Rev Recd Date: 11 July 2018
  • Publish Date: 31 August 2018
  • 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.
    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.
  • loading
  • [1]
    HELLWIG A, VOLKMANN L. Maximally edge-connected and vertex-connected graphs and digraphs: A survey[J]. Discrete Mathematics, 2008, 308: 3265-3296.
    [2]
    GELLER D, HARARY F. Connectivity in digraphs[C]// Recent Trends in Graph Theory. Berlin/ Heidelberg: Springer, 1971, 186: 105-115.
    [3]
    CHARTRAND G, HARARY F. Graphs with prescribed connectivities[C]// Theory of Graphs. London/ New York/ San Francisco: Academic Press, 1968: 61-63.
    [4]
    BALBUENA C, CARMONA A. On the connectivity and superconnectivity of bipartite digraphs and graphs[J]. Ars Combinatoria, 2001, 61: 3-21.
    [5]
    FBREGA J, FIOL M A. Maximally connected digraphs[J]. Journal of Graph Theory, 1989, 13: 657-668.
    [6]
    HELLWIG A, VOLKMANN L. Lower bounds on the vertex-connectivity of digraphs and graphs[J]. Information Processing Letters, 2006, 99: 41-46.)
  • 加载中

Catalog

    [1]
    HELLWIG A, VOLKMANN L. Maximally edge-connected and vertex-connected graphs and digraphs: A survey[J]. Discrete Mathematics, 2008, 308: 3265-3296.
    [2]
    GELLER D, HARARY F. Connectivity in digraphs[C]// Recent Trends in Graph Theory. Berlin/ Heidelberg: Springer, 1971, 186: 105-115.
    [3]
    CHARTRAND G, HARARY F. Graphs with prescribed connectivities[C]// Theory of Graphs. London/ New York/ San Francisco: Academic Press, 1968: 61-63.
    [4]
    BALBUENA C, CARMONA A. On the connectivity and superconnectivity of bipartite digraphs and graphs[J]. Ars Combinatoria, 2001, 61: 3-21.
    [5]
    FBREGA J, FIOL M A. Maximally connected digraphs[J]. Journal of Graph Theory, 1989, 13: 657-668.
    [6]
    HELLWIG A, VOLKMANN L. Lower bounds on the vertex-connectivity of digraphs and graphs[J]. Information Processing Letters, 2006, 99: 41-46.)

    Article Metrics

    Article views (32) PDF downloads(82)
    Proportional views

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return