In this note we give a slight extension of Mader's undirected splitting-off theorem with a simple proof, and we investigate some related questions. Frank used Mader's theorem for solving the local edge-connectivity augmentation problem which is the following: given a graph $G_0=(V,E_0)$ and a symmetric function $r:V \times V \to \Zset_+$, find a graph $G=(V,E)$ with a minimum number of edges such that $\lambda_{G_0+G}(u,v) \geq r(u,v)$ for every pair of nodes $u,v$. In the solution Frank introduces the set function $R_r(X)=\max\{r(x,y):x\in X,y\in V-X\}$ for any $X\subseteq V$ and he reproves Mader's theorem using the following three properties of this function: (i) symmetry, (ii) skew-supermodularity and (iii) $R_r(X\cup Y)\le \max\{R_r(X),R_r(Y)\}$ for every pair of sets $X,Y\subseteq V$. We give a proof where (iii) is only required for disjoint pairs of sets $X,Y\subseteq V$, and we show examples of functions satisfying Properties (i)-(ii) and this weaker form of (iii).
Bibtex entry:
@techreport{egres-11-10,
AUTHOR | = | {Bern{\'a}th, Attila and Kir{\'a}ly, Tam{\'a}s and V{\'e}gh, L{\'a}szl{\'o}}, |
TITLE | = | {Special skew-supermodular functions and a generalization of Mader's splitting-off theorem}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2011}, |
NUMBER | = | {TR-2011-10} |