Detachments Preserving Local Edge-Connectivity of Graphs Tibor Jordán Zoltán Szigeti November 1999

### Abstract:

Let be a graph and let be a set of positive integers with . An -detachment splits into a set of independent vertices with , . Given a requirement function on pairs of vertices of , an -detachment is called -admissible if the detached graph satisfies for every pair . Here denotes the local edge-connectivity between and in graph .

We prove that an -admissible -detachment exists if and only if (a) , and (b) hold for every .

The special case of this characterization when for each pair in was conjectured by B. Fleiner. Our result is a common generalization of a theorem of W. Mader on edge splittings preserving local edge-connectivity and a result of B. Fleiner on detachments preserving global edge-connectivity. Other corollaries include previous results of L. Lovász and C. J. St. A. Nash-Williams on edge splittings and detachments, respectively. As a new application, we extend a theorem of A. Frank on local edge-connectivity augmentation to the case when stars of given degrees are added

Available as PostScript, PDF, DVI.