### Constrained Edge-Splitting Problems

#### Abstract

Splitting off two edges su, sv in a graph G means deleting su, sv and

adding a new edge uv. Let G = (V +s,E) be k-edge-connected in V

(k >= 2) and let d(s) be even. Lov´asz proved that the edges incident to s

can be split off in pairs in such a way that the resulting graph on vertex

set V is k-edge-connected. In this paper we investigate the existence of

such complete splitting sequences when the set of split edges has to meet

additional requirements. We prove structural properties of the set of those

pairs u, v of neighbours of s for which splitting off su, sv destroys k-edge-connectivity. This leads to a new method for solving problems of this type.

By applying this method we obtain a short proof for a recent result of

Nagamochi and Eades on planarity-preserving complete splitting sequences and prove the following new results: let G and H be two graphs on the same set V + s of vertices and suppose that their sets of edges incident to s coincide. Let G (H) be k-edge-connected (l-edge-connected, respectively) in V and let d(s) be even. Then there exists a pair su, sv which can be split off in both graphs preserving k-edge-connectivity (l-edge-connectivity, resp.) in V , provided d(s) >= 6. If k and l are both even then such a pair always exists. Using these edge-splitting results and the polymatroid intersection theorem we give a polynomial algorithm for the problem of simultaneously augmenting the edge-connectivity of two graphs by adding a (common) set of new edges of (almost) minimum size.

#### Full Text:

PDFDOI: http://dx.doi.org/10.7146/brics.v6i37.20106

ISSN: 0909-0878

Hosted by the State and University Library and Aarhus University Library