J. Bang-jensen et T. Jordan, Splitting off edges within a specified subset preserving the edge-connectivity of the graph, J ALGORITHM, 37(2), 2000, pp. 326-343
Splitting off a pair su, sv of edges in a graph G means the operation that
deletes sa and sv and adds a new edge uv. Given a graph G = (V + s, E) whic
h is kedge-connected (k greater than or equal to 2) between vertices of V a
nd a specified subset R subset of or equal to V, first we consider the prob
lem of finding a longest possible sequence of disjoint pairs of edges sx, s
y, (x, y is an element of R) which can be split off preserving k-edge-conne
ctivity in V. If R = V and d(s) is even then a well-known theorem of Lovasz
asserts that a complete R-splitting exists, that is, all the edges connect
ing s to R can be split off in pairs. This is nor the case in general. We c
haracterize the graphs possessing a complete R-splitting and give a formula
for the length of a longest R-splitting sequence. Motivated by the connect
ion between splitting off results and connectivity augmentation problems we
also investigate the following problem that we call the split completion p
roblem: given G and R as above, find a smallest set F of new edges incident
to s such that G' = (V + s, E + F) has a complete R-splitting. We give a m
in-maw formula for \F\ as well as a polynomial algorithm to find a smallest
F. As a corollary we show a polynomial algorithm which finds a solution of
size at most k/2 + 1 more than the optimum for the following augmentation
problem, raised in [2]: given a graph H = (V, E), an integer k greater than
or equal to 2, and a set R subset of or equal to V, find a smallest set F'
of new edges for which H' =(C: Ef F') is k-edge-connected and no edge of F
' crosses R. (C) 2000 Academic Press.