Disjoint shortest paths in graphs
A set of paths \(\{P_ 1,...,P_ n\}\) is called a linkage iff any two distinct members are vertex disjoint. A linkage is said to be a geodetic linkage if each path is a geodesic. A graph is n-geodetically connected if it is connected and the removal of any n-1 vertices does not increase the distance between any two remaining vertices. Using a characterization of n-geodetically connected graphs by the reviewer, \textit{D. E. Jackson} and \textit{P. J. Slater} [IEEE Trans. Circuits Syst. 24, 460-463 (1977; Zbl 0344.05137)] the authors obtain the following result. Let \(n\geq 1\) and \(x_ 1,...,x_ n,y_ 1,...,y_ n\) be distinct vertices of G. Suppose \(| \{i| d_ G(x_ 1,y_ i)=2\}| =q\geq 1\) and G is \((2n+q-2)\)-geodetically connected. Then there exists a geodetic linkage \(\{P_ 1[x_ 1;y_ 1],...,P_ n[x_ n;y_ n]\}\). A separate result for the case \(q=0\) is also obtained. The results are shown to be best possible.
- Disjoint paths in symmetric digraphs
- Short disjoint paths in locally connected graphs
- Shortest Paths between Shortest Paths and Independent Sets
- scientific article; zbMATH DE number 4110723 (Why is no real title available?)
- Towards minimumk-geodetically connected graphs
- Shortest edge-disjoint paths in graphs
- The Directed Disjoint Shortest Paths Problem
This page was built for publication: Disjoint shortest paths in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q762495)
