Wide-diameter and minimum length of fan
Let k be a positive integer and let G be a graph with \ V(G)\ greater than or equal to k + 1. For two distinct vertices x,y is an element of V(G), the k-wide-distance between x and y is the minimum l such that there exist k vertex-disjoint (x,y)-paths whose lengths are at most l. The k-wide-diameter d(k)(G) of G is the maximum value of the Ic-wide-distance between two distinct vertices of G. For x(0) is an element of V(G) and k distinct vertices x(1,)x(2),...,x(k) is an element of V(G) - {x(0)}, we define f(k)(x(0),{x(1),x(2),...,x(k)}) to be the minimum I such that there exist k vertex-disjoint paths P-1,P-2,..,P-k, where P-i is an (x(0),x(i))-path of length at most l. We define f(k)(G) to be the maximum value of f(k)(x(0), {x(1),x(2),...,x(k)}) over every x(0) is an element of V(G) and k distinct vertices x(1),x(2),...,x(k) is an element of V(G)- {x(0)}. We study relationships between dk(G) and fk(G). Among other results, we show that if G is a k-connected graph, k greater than or equal to 2, then d(k)(G) - 1 less than or equal to f(k)(G)less than or equal to max{d(k)(G),(k - 1)d(k)(G) - 4k + 7}. (C) 2000 Elsevier Science B.V. All rights reserved.
wide-diameter length fan graph wide-distance