Wide diameter and minimum length of disjoint menger path systems
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 I such that there exist k internally disjoint (x, y)paths whose lengths are at most I. We define d(k)(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 m(k)(X, Y) to be the minimum integer I such that there exist k vertex-disjoint (X, Y)-paths of length at most 1, 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 d(k) (G) - 2 <= m(k) (G) [GRAPHICS] (c) 2005 Wiley Periodicals, Inc.
wide diameter length menger path system graph wide distance