TR-2002-10

Minimally k-edge-connected directed graphs of maximal size

Alex Berg, Tibor Jordán

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



Abstract

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:

@techreport{egres-02-10,
AUTHOR = {Berg, Alex and Jord{\'a}n, Tibor},
TITLE = {Minimally $k$-edge-connected directed graphs of maximal size},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2002},
NUMBER = {TR-2002-10}
}


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