Detachments Preserving Local Edge-Connectivity of Graphs

Tibor Jordán
Zoltán Szigeti

November 1999

Abstract:

Let $G=(V+s,E)$ be a graph and let ${\cal S}=(d_1,...,d_p)$ be a set of positive integers with $\sum d_j=d(s)$. An $\cal S$-detachment splits $s$ into a set of $p$ independent vertices $s_1,...,s_p$ with $d(s_j)=d_j$, $1\leq j\leq p$. Given a requirement function $r(u,v)$ on pairs of vertices of $V$, an $\cal S$-detachment is called $r$-admissible if the detached graph $G'$ satisfies $\lambda_{G'}(x,y)\geq r(x,y)$ for every pair $x,y\in V$. Here $\lambda_H(u,v)$ denotes the local edge-connectivity between $u$ and $v$ in graph $H$.

We prove that an $r$-admissible $\cal S$-detachment exists if and only if (a) $\lambda_G(x,y)\geq r(x,y)$, and (b) $\lambda_{G-s}(x,y)\geq r(x,y)-\sum \lfloor d_j/2 \rfloor$ hold for every $x,y\in V$.

The special case of this characterization when $r(x,y)=\lambda_G(x,y)$ for each pair in $V$ 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 PostScript, PDF, DVI.

Last modified: 2003-06-08 by webmaster.