Sufficient Conditions for Maximally Edge-connected and Super-edge-connected Digraphs Depending on the Size  

作　　者：Sebastian MILZ Lutz VOLKMANN 

机构地区：[1]Lehrstuhl Ⅱ für Mathematik, RWTH Aachen University

出　　处：《Acta Mathematica Sinica,English Series》2019年第12期1861-1870,共10页数学学报（英文版）

摘　　要：Let D be a finite and simple digraph with vertex set V(D).The minimum degreeδof a digraph D is defined as the minimum value of its out-degrees and its in-degrees.If D is a digraph with minimum degreeδand edge-connectivity λ,then λ≤δ.A digraph is maximally edge-connected ifλ=δ.A digraph is called super-edge-connected if every minimum edge-cut consists of edges incident to or from a vertex of minimum degree.In this note we show that a digraph is maximally edge-connected or super-edge-connected if the number of arcs is large enough.Let D be a finite and simple digraph with vertex set V(D). The minimum degree δ of a digraph D is defined as the minimum value of its out-degrees and its in-degrees. If D is a digraph with minimum degree δ and edge-connectivity λ, then λ ≤ δ. A digraph is maximally edge-connected if λ = δ. A digraph is called super-edge-connected if every minimum edge-cut consists of edges incident to or from a vertex of minimum degree. In this note we show that a digraph is maximally edge-connected or super-edge-connected if the number of arcs is large enough.

关 键 词：DIGRAPHS EDGE-CONNECTIVITY MAXIMALLY edge-connected DIGRAPHS super-edge-connected DIGRAPHS 

分 类 号：O15[理学—数学]