ISSN 0253-2778

CN 34-1054/N

open

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

  • 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

Catalog

    {{if article.pdfAccess}}
    {{if article.articleBusiness.pdfLink && article.articleBusiness.pdfLink != ''}} {{else}} {{/if}}PDF
    {{/if}}
    XML

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return