On a theorem of Mader (Q1197013)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On a theorem of Mader |
scientific article; zbMATH DE number 89889
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On a theorem of Mader |
scientific article; zbMATH DE number 89889 |
Statements
On a theorem of Mader (English)
0 references
16 January 1993
0 references
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 [\textit{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.
0 references
theorem of Mader
0 references
multigraph
0 references
edge-connectivity
0 references
splittable pair
0 references
0.79327214
0 references
0 references
0 references
0.7706535
0 references
0.7680234
0 references
0.76010597
0 references
0.75959444
0 references
0 references