On the Rabin number problem
Dyi‐Rong Duh, Gen-Huey Chen · Networks · 1997
Given positive integers κ and l, let R(κ, l) denote the class of interconnection networks so that for any κ + 1 distinct nodes x, y1, y2, …, yκ there exist κ node-disjoint paths (except at x) of length at most l from x to y1, y2, …, yκ, respectively. The Rabin number of a network W with connectivity κ, denoted by rκ(W), is defined as min{l|W ∈ R(κ, l)}. The Rabin number problem is to compute rκ(W) for a given network W. Computing Rabin numbers for nontrivial networks is not easy, in general. Thus far, only the Rabin number of the hypercube has been computed. In this paper, some new results on the Rabin number problem are derived. First, a theorem relating the Rabin number with both wide diameter and fault diameter is obtained. This theorem can help in the derivation of lower bounds for the Rabin numbers of circulant networks, folded hypercubes, hierarchical folded-hypercube networks, generalized hypercubes, and WK-recursive networks. Moreover, upper bounds are also obtained for WK-recursive networks and a special class of generalized hypercubes. The Rabin numbers of a special class of circulant networks and a special class of generalized hypercubes are determined as a consequence of the derived upper and lower bounds. © 1997 John Wiley & Sons, Inc. Networks 30:219–230, 1997