TR-2002-01

Detachment of vertices of graphs preserving edge-connectivity

Balázs Fleiner

Published in:
SIAM J. Discrete Math. 18 (2004) 581-591

The detachment of vertex is the inverse operation of merging vertices s₁,...,s_t into s. We speak about { d₁,...,d_t}-detachment if for the detached graph G' the new degrees are specified as d_G'(s₁)=d₁,...,d_G'(s_t)=d_t. We call a detachment k-feasible if d_G'(X) \geq k whenever X separates two vertices of V(G)-s. In our main theorem, we give a necessary and sufficient condition for the existence of a k-feasible { d₁,...,d_t}-detachment of vertex s. This theorem also holds for graphs containing 3-vertex hyperedges disjoint from s. From special cases of the theorem, we get a characterization of those graphs whose edge-connectivity can be augmented to k by adding \gamma edges and p 3-vertex hyperedges. We give a new proof for the theorem of Nash-Williams that characterizes the existence of a simultaneous detachment of the vertices of a given graph such that the resulted graph is k-edge-connected.

Bibtex entry:

@techreport{egres-02-01,

AUTHOR	=	{Fleiner, Bal{\'a}zs},
TITLE	=	{Detachment of vertices of graphs preserving edge-connectivity},
NOTE	=	{{\tt www.cs.elte.hu/egres}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2002},
NUMBER	=	{TR-2002-01}

}