Minimally k-edge-connected directed graphs of maximal size

Alex Berg, Tibor Jordán

Published in:
Graphs Combin. 21 (2005) 39-50.


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.

Bibtex entry:

AUTHOR = {Berg, Alex and Jord{\'a}n, Tibor},
TITLE = {Minimally $k$-edge-connected directed graphs of maximal size},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2002},
NUMBER = {TR-2002-10}

Last modification: 29.12.2020. Please email your comments to Tamás Király!