On strong Menger-connectivity of star graphs

Motivated by parallel routing in networks with faults, we study the following graph theoretical problem. Let G be a graph of minimum vertex degree d. We say that G is strongly Menger-connected if for any copy G(f) of G with at most d - 2 nodes removed, every pair of nodes u and v in G(f) are connected by min{deg(f)(u),deg(f)(v)} node-disjoint paths in G(f), where deg(f)(u) and deg(f)(v) are the degrees of the nodes u and v in G(f), respectively. We show that the star graphs, which are a recently proposed attractive alternative to the widely used hypercubes as network models, are strongly Menger-connected. An algorithm of optimal running time is developed that constructs the maximum number of node-disjoint paths of nearly optimal length in star graphs with faults. (C) 2002 Elsevier B.V. All rights reserved.