Wide diameter and minimum length of disjoint Menger path systems
Toru Kojima · Networks · 2005
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 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 © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(3), 136–141 2005