Minimally k-Edge-Connected Directed Graphs of Maximal Size

Let D=(V,E) be a minimally k-edge-connected simple directed graph. We prove that there is a function f(k) such that |V|f(k) implies |E|2k(|V|–k). We also determine the extremal graphs whose size attains this upper bound.Basic Research in Computer Science, funded by the Danish National Research Foundation.Supported by the MTA-ELTE Egerváry Research Group on Combinatorial Optimization, and the Hungarian Scientific Research Fund grant No. F034930, T037547, and FKFP grant No. 0143/2001. Part of this research was done when the second author visited BRICS, University of Aarhus, Denmark.