Mader's splitting-off theorem
In an undirected graph G we denote by [math]\lambda_G(u,v)[/math] the maximum number of edge-disjoint paths between nodes u and v.
Theorem (Mader [1]). Let G=(V+s,E) be a connected undirected graph where the degree of s is not 3 and s is not incident to bridges. Then there are two edges incident to s that can be split off such that in the resulting graph [math]G'[/math] we have [math]\lambda_{G'}(u,v)=\lambda_G(u,v)[/math] for any [math]u\in V[/math] and [math]v\in V[/math].
There is a directed splitting-off theorem due to Mader, too, but it concerns only global edge-connectivity.
Theorem (Mader [2]). Let D=(V+s,A) be a directed graph with [math]\varrho_D(s)=\delta_D(s)[/math] which is k-arc-connected in V for some positive integer k. Then for any arc [math]st\in A[/math] incident to s there exists another arc [math]zs\in A[/math] such that splitting off this pair of arcs the resulting graph is again k-arc-connected in V.
For a survey on applications and generalizations, see [3].
References
- ↑ W. Mader, A reduction method for edge-connectivity in graphs, Ann. Discrete Math. 3 (1978), 145-164, Google Books link
- ↑ W. Mader, Konstruktion aller n-fach kantenzusammenhängenden Digraphen, Europ. J. Combinatorics 3 (1982), 63-67, DOI link
- ↑ A. Frank, Edge-connection of graphs, digraphs, and hypergraphs, DOI link, EGRES Technical report
