TR-2004-07

On admissible edges

Zoltán Szigeti

Let G=(V+s,E) be a 2-edge-connected graph. A pair of edges rs, st is called admissible if splitting off these edges (replacing rs and st by rt) preserves the local edge connectivities between all pairs of vertices in V.
 
First we generalize Mader's result [2] by showing that if d(s)> 3 then there exists an edge that belongs to at least \lfloor {d(s)\over 3} \rfloor admissible pairs. An infinite family of graphs shows that this is best possible.
 
Second we generalize Frank's result [1] by characterizing when an edge belongs to no admissible pairs. It provides a new proof for Mader's theorem.

Bibtex entry:

@techreport{egres-04-07,

AUTHOR	=	{Szigeti, Zolt{\'a}n},
TITLE	=	{On admissible edges},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2004},
NUMBER	=	{TR-2004-07}

}