Constructing vertex-disjoint paths in (n,k)-star graphs

[[abstract]]This work describes a novel routing algorithm for constructing a container of width n - 1 between a pair of vertices in an (n, k)-star graph with connectivity it - 1. Since Lin et al. [T.C. Lin, D.R. Duh, H.C. Cheng, Wide diameter of (n, k)-star networks, in: Proceedings of the International Conference on Computing, Communications and Control Technologies, vol. 5, 2004 pp. 160-165] already calculated the wide diameters in (n, n - 1)-star and (n, 1)-star graphs, this study only considers an (n, k)-star with 2 <= k <= n - 2. The length of the longest container among all constructed containers serves as the upper bound of the wide diameter of an (n, k)-star graph. The lower bound of the wide diameter of an (n, k)-star graph with 2 <= k <= [n/2] and the lower bound of the wide diameter of a regular graph with a connectivity of 2 or above are also computed. Measurement results indicate that the wide diameter of an (n, k)-star graph is its diameter plus 2 for 2 <= k <= [n/2], or its diameter plus a value between 1 and 2 for [n/2] + 1 <= k <= n - 2. (c) 2007 Elsevier Inc. All rights reserved.[[note]]SC