On strong Menger-connectivity of star graphs

✍ Scribed by Eunseuk Oh; Jianer Chen

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 415 KB
• Volume: 129
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(02)00600-5

✦ Synopsis

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.