Disjoint paths in graphs. (Reprint)

DOI10.1016/J.DISC.2006.03.019MaRDI QIDQ2497998zbMATH OpenOpenAlexFDO

Authors Paul Seymour

Publication date 4 August 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2006.03.019

zbMATH Keywords

edge disjoint pathsMenger's theoremvertex disjoint paths

Mathematics Subject Classification ID

Paths and cycles (05C38)

Review text

Reprint of an important article published in Discrete Math. 29, 293--309 (1980; Zbl 0457.05043). Generalizations of both edge (and vertex) versions of Menger's theorem on the number of edge disjoint (vertex disjoint) paths between a pair of vertices of a graph are proved. Let \((x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)\) be \(k\) pairs of vertices of a graph \(G\). Necessary and sufficient conditions for the existence of edge disjoint (vertex disjoint) paths between \(x_i\) and \(y_i\) for \(1 \leq i \leq k\) are proved when either \(k = 2\) or when \(| \{x_1, y_1, x_2, y_2, \dots, x_k, y_k\}| = 3\).

Recommendations

• Paths and edge-connectivity in graphs
• Disjoint Paths in a Planar Graph—A General Theorem
• scientific article; zbMATH DE number 4089593
• Menger's theorem
• A mixed version of Menger's theorem

Cites work

• A short proof of the two-commodity flow theorem
• Four-terminus flows
• Multi-Commodity Network Flows
• On Odd Cuts and Plane Multicommodity Flows
• On the Complexity of Timetable and Multicommodity Flow Problems
• The directed subgraph homeomorphism problem
• The subgraph homeomorphism problem
• Über die Maximalzahl kantendisjunkter A-Wege

Cited in

(27)

• Disjoint paths in symmetric digraphs
• Disjoint edge paths between given vertices of a convex polytope
• Disjoint paths in graphs. I: 3-planar graphs and basic obstructions
• Disjoint paths in graphs. II: A special case
• Disjoint paths in graphs. III: Characterization
• Reconstructing edge-disjoint paths.
• A short proof of Mader's \(\mathcal S\)-paths theorem
• Disjoint non-balanced A-paths in biased graphs
• On finding Min-Min disjoint paths
• Disjoint path covers joining prescribed source and sink sets in interval graphs
• Disjoint A-paths in digraphs
• Note on Whitney's theorem for k-connected graphs
• Hardness of finding two edge-disjoint Min-Min paths in digraphs
• A generalization of an important lemma related to the Murty-Simon conjecture
• Mader tools
• scientific article; zbMATH DE number 4023311 (Why is no real title available?)
• Vertex-disjoint paths and edge-disjoint branchings in directed graphs
• scientific article; zbMATH DE number 4089593 (Why is no real title available?)
• Disjoint Paths in a Planar Graph—A General Theorem
• scientific article; zbMATH DE number 524123 (Why is no real title available?)
• On the complexity of the edge-disjoint min-min problem in planar digraphs
• Local edge and local node connectivity in regular graphs
• A proof of Menger's Theorem by contraction
• scientific article; zbMATH DE number 2188351 (Why is no real title available?)
• LATIN 2004: Theoretical Informatics
• Graph-Theoretic Concepts in Computer Science
• Paths and edge-connectivity in graphs

This page was built for publication: Disjoint paths in graphs. (Reprint)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2497998)