Strong Rabin numbers of folded hypercubes

The strong Rabin number of a network W of connectivity k is the minimum l so that for any k+1 nodes s, d1,d2,…,dk of W, there exist k node-disjoint paths from s to d1,d2,…,dk, respectively, whose maximal length is not greater than l, where s∉{d1,d2,…,dk} and d1,d2,…,dk are not necessarily distinct. In this paper, we show that the strong Rabin number of a k-dimensional folded hypercube is ⌈k/2⌉+1, where ⌈k/2⌉ is the diameter of the k-dimensional folded hypercube. Each node-disjoint path we obtain has length not greater than the distance between the two end nodes plus two. This paper solves an open problem raised by Liaw and Chang.