zbMATH — the first resource for mathematics

On a theorem of Mader. (English) Zbl 0789.05051
For vertices \(x\), \(y\) in a multigraph \(G\), \(\lambda(x,y;G)\) denotes the maximal number of edge-disjoint \(x,y\)-paths in \(G\). Let \(G\) be a finite multigraph and let \(s\) be a vertex in \(G\) of degree \(d(s) \neq 0,3\) not incident to a bridge. For edges \(e_ i\) joining \(s\) and \(x_ i\) for \(i=1,2\), \(G^{e_ 1e_ 2}\) arises from \(G\) by deleting \(e_ 1\), \(e_ 2\), and, if \(x_ 1 \neq x_ 2\), by adding a new edge between \(x_ 1\) and \(x_ 2\). It was proved in [W. Mader, A reduction method for edge-connectivity in graphs, Ann. Discrete Math. 3, 145-164 (1978; Zbl 0389.05042)] that there are edges \(e_ 1 \neq e_ 2\) incident to \(s\) such that \(\lambda (x,y;G^{e_ 1e_ 2})=\lambda (x,y;G)\) for all vertices \(x,y\) from \(G-s\). Such a pair of edges is called a splittable pair at \(s\). Now a relatively simple proof of this result is given, and it is shown that for \(d(s) \neq 3\) there are \(\lfloor {d(s) \over 2} \rfloor\) disjoint splittable pairs at \(s\), whereas from the above result one gets for odd \(d(s)\) only \({d(s)-3 \over 2}\) such pairs.
Reviewer: W.Mader (Hannover)

05C40 Connectivity
Full Text: DOI
[1] Ford, L.R.; Fulkerson, D.R., Flows in networks, (1962), Princeton Univ. Press Princeton, NJ · Zbl 0139.13701
[2] Frank, A., Augmenting graphs to meet edge-connectivity requirements, SIAM J. discrete math., 5, 1, 25-53, (1992) · Zbl 0782.05054
[3] Lovász, L., Lecture on a conference on graph theory, (1974), Prague
[4] Lovász, L., Combinatorial problems and exercises, (1979), North-Holland Amsterdam · Zbl 0439.05001
[5] Mader, W., A reduction method for edge-connectivity in graphs, Ann. discrete math., 3, 145-164, (1978) · Zbl 0389.05042
[6] Menger, K., Zur allgemeinen kurventheorie, Fund. math., 10, 96-115, (1927) · JFM 53.0561.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.