Constrained Edge-Splitting Problems
Tibor Jordán November 1999 |
Abstract:
Splitting off two edges in a graph means deleting
and adding a new edge . Let be -edge-connected in
() and let be even. Lovász proved that the edges
incident to can be split off in pairs in a such a way that the resulting
graph on vertex set is -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 of neighbours of for which splitting off
destroys -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 and be two graphs on the same set of vertices and suppose that their sets of edges incident to coincide. Let () be -edge-connected (-edge-connected, respectively) in and let be even. Then there exists a pair which can be split off in both graphs preserving -edge-connectivity (-edge-connectivity, resp.) in , provided . If and 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 Available as PostScript, PDF, DVI. |