|
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:
| 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 egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2011}, |
| NUMBER | = | {TR-2011-10} |