Premium
w ‐Rabin numbers and strong w ‐Rabin numbers of folded hypercubes
Author(s) -
Lai ChengNan,
Chen GenHuey
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20213
Subject(s) - hypercube , combinatorics , multiset , disjoint sets , mathematics , node (physics) , shortest path problem , discrete mathematics , path (computing) , graph , computer science , physics , quantum mechanics , programming language
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