Some problems related to constrained length connectivity are addressed in this paper. Let S-l(x, y) be the minimum number of vertices that should be removed to destroy all the paths of length at most l between two vertices x and y. Let I-l(x, y) be the maximum number of such node-disjoint paths. We first focus on f(l, d), defined as the supremum of (S-l(x, y))/(I-l(x, y)) taken over all graphs and all pairs of x, y separated by a distance d. One of the results shown in this paper states that this supremum is exactly equal to l + 1 - d when d greater than or equal to [2/3(l + 1)] and is at least constant when 2 less than or equal to d less than or equal to 2 + [(l + 1)/3]. Some classes of two connected graphs satisfying path-length constraints are defined. Most of them describe survivable telecommunication networks. Relationships between flows and constrained length connectivity are addressed. We also study the minimum edge numbers of these two connected graphs. Some of their topological properties are presented. (C) 2000 John Wiley & Sons, Inc.
