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.

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 egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2002},
NUMBER	=	{TR-2002-10}

}