Bounds on path connectivity
A graph is k-path-connected if it has at least 2k vertices and, for any k pairs of distinct vertices, there are k disjoint paths connecting them. The authors prove a result implying the existence of a function f(d) such that no planar graph of maximum degree d is f(d)-path-connected. For edge-connectivity the following interpolation theorem is proved: Let \(s_ 1,t_ 1,s_ 2,t_ 2\) be vertices such that, for each \(i=1,2\), there are k edge-disjoint paths between \(s_ i\) and \(t_ i\) and let m be any natural number less than k. Then the graph contains a collection of m edge-disjoint paths such that m or \(m+1\) of these connect \(s_ 1\) and \(t_ 1\) and the others connect \(s_ 2\) and \(t_ 2\).
- 2-linked graphs
- Disjoint paths in graphs
- Edge-Disjoint Spanning Trees of Finite Graphs
- Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
- scientific article; zbMATH DE number 3648730 (Why is no real title available?)
- scientific article; zbMATH DE number 3947966 (Why is no real title available?)
- scientific article; zbMATH DE number 3550190 (Why is no real title available?)
- On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
- On the Problem of Decomposing a Graph into n Connected Factors
- Universality considerations in VLSI circuits
- The maximal size of graphs with at most \(k\) edge-disjoint paths connecting any two adjacent vertices
- The \(k\)-subconnectedness of planar graphs
- On the maximum degree of path-pairable planar graphs
- scientific article; zbMATH DE number 1744097 (Why is no real title available?)
- Paths with restricted degrees of their vertices in planar graphs
- Tight bounds for connecting sites across barriers
This page was built for publication: Bounds on path connectivity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q761468)
