On a theorem of Mader
type: Item
instance of: scholarly article
title: On a theorem of Mader
zbMATH Open document ID: 0789.05051
DOI: 10.1016/0012-365X(92)90589-8
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: 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.
reviewed by: W. Mader
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 89889
zbMATH Keywords: theorem of Mader
zbMATH Keywords: multigraph
zbMATH Keywords: edge-connectivity
zbMATH Keywords: splittable pair
Wikidata QID: Q56987168
author: András Frank
MaRDI profile type: Publication
cites work: Q5514188
cites work: Augmenting Graphs to Meet Edge-Connectivity Requirements
cites work: Q3880849
cites work: A Reduction Method for Edge-Connectivity in Graphs
Recommended article: Paths in graphs, reducing the edge-connectivity only by two
Recommended article: Path decompositions of multigraphs
Recommended article: Q3015590
Recommended article: Decomposition of multigraphs
Recommended article: The complete graph \(t\)-packings and \(t\)-coverings
Recommended article: Hamilton path decompositions of complete multipartite graphs
Recommended article: Paths and edge-connectivity in graphs. III: Six-terminal k paths
Recommended article: Decomposing graphs into paths of fixed length
Recommended article: Paths and edge-connectivity in graphs
description: scientific article; zbMATH DE number 89889