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 the normal view instead:

scientific article; zbMATH DE number 89889
Language Label Description Also known as
default for all languages
No label defined
    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
      0 references
      theorem of Mader
      0 references
      multigraph
      0 references
      edge-connectivity
      0 references
      splittable pair
      0 references
      0 references

      Identifiers