<i>w</i>‐Rabin numbers and strong <i>w</i>‐Rabin numbers of folded hypercubes

Abstract

Abstract The w ‐Rabin number of a network W is the minimum l so that for any w + 1 distinct nodes s , d 1 , d 2 ,…, d w of W , there exist w node‐disjoint paths from s to d 1 , d 2 ,…, d w , respectively, whose maximal length is not greater than l , where w is not greater than the node connectivity of W . If { d 1 , d 2 ,…, d w } is allowed to be a multiset, then the resulting minimum l is called the strong w ‐Rabin number of W . In this article, we show that both the w ‐Rabin number and the strong w ‐Rabin number of a k ‐dimensional folded hypercube are equal to ⌈ k /2⌉ for 1 ≤ w ≤ ⌈ k /2⌉‐ 1, and ⌈ k /2⌉+ 1 for ⌈ k /2⌉ ≤ w ≤ k + 1, where k ≥ 5. Each path obtained is shortest or second shortest. The results of this paper also solve an open problem raised by Liaw and Chang. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008