Detachment of Vertices of Graphs Preserving Edge-Connectivity
Balázs Fleiner · SIAM Journal on Discrete Mathematics · 2004
The detachment of vertex is the inverse operation of merging vertices s 1 ,... ,s t into s. We speak about {d 1 ,... ,d t }-detachment if, for the detached graph G', the new degrees are specified as d G' (s 1 )=d 1 ,...,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 1 ,... ,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 resulting graph is k-edge-connected.