Disjoint shortest paths in graphs (Q762495)

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.