Detachments Preserving Local Edge-Connectivity of Graphs
Tibor Jordán, Zoltán Szigeti · SIAM Journal on Discrete Mathematics · 2003
Let G=(V+s,E) be a graph with a designated vertex s of degree d(s), and let f(s)=(d 1 ,d 2 ,. . .,d p ) be a partition of d(s) into p positive integers. An f(s)-detachment of G is a graph G' obtained by "splitting" s into p vertices, called the pieces of s, such that the degrees of the pieces of s in G' are given by f(s). Thus every edge $sw\in E$ corresponds to an edge of G' connecting some piece of s to w. We give necessary and sufficient conditions for the existence of an f(s)-detachment of G in which the local edge-connectivities between pairs of vertices in V satisfy prespecified lower bounds. Our result is a common generalization of a theorem of Mader on edge splittings preserving local edge-connectivities and a result of Fleiner on f(s)-detachments satisfying uniform lower bounds. It implies a conjecture of Fleiner on f(s)-detachments preserving local edge-connectivities. By using our characterization we extend a theorem of Frank on local edge-connectivity augmentation of graphs to the case when stars of given degrees are added, and we also solve the local edge-connectivity augmentation problem for 3-uniform hypergraphs.