Detachments Preserving Local Edge-Connectivity of Graphs
Tibor Jordán
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 |

Last modified: 2003-06-08 by webmaster.