Let k be a positive integer and let G be a graph with at least k + 1 vertices. For two distinct vertices x,y of G, the k-wide distance dk(x,y) between x and y is the minimum integer l such that there exist k internally disjoint (x,y)-paths whose lengths are at most l. We define dk(x,x) = 0. The k-wide diameter dk(G) of G is the maximum value of the k-wide distances between two vertices of G. Let X,Y be k-subsets of V(G). We define mk(X,Y) to be the minimum integer l such that there exist k vertex-disjoint (X,Y)-paths of length at most l, and we define mk(G) to be the maximum value of mk(X,Y) over all k-subsets X,Y of V(G). We study relationships between dk(G) and mk(G). Among other results, we show that if k ≥ 2 and G is a k-connected graph, then $$\eqalign{d_k(G)-2 & \leq m_k(G)\cr & \leq \cases{d_k(G) & $\hbox{if}\ d_k(G) \leq 3,$ \cr k+2 & $\hbox{if}\ d_k(G) = 4,$ \cr {{k(k-1)} \over {2}}d_k(G) - 2(k^2-k-2) & $\hbox{if}\ d_k(G) \geq 5.$}}$$ © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(3), 136–141 2005
['Toru Kojima']
Wide diameter and minimum length of disjoint Menger path systems