Wide diameter and minimum length of disjoint Menger path systems

Abstract 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 d k ( 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 d k ( x , x ) = 0. The k ‐wide diameter d k ( 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 m k ( 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 m k ( G ) to be the maximum value of m k ( X , Y ) over all k ‐subsets X , Y of V ( G ). We study relationships between d k ( G ) and m k ( 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