×

zbMATH — the first resource for mathematics

Minimally \(k\)-edge-connected directed graphs of maximal size. (English) Zbl 1062.05079
Summary: 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| \geq f(k)\) implies \(|E| \leq 2k(|V|-k)\). We also determine the extremal graphs whose size attains this upper bound.

MSC:
05C40 Connectivity
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI