Embedding Star Networks into Hypercubes

The star interconnection network has recently been suggested as an alternative to the hypercube. As hypercubes are often viewed as universal and capable of simulating other architectures efficiently, we investigate embeddings of star network into hypercubes. Our embeddings exhibit a marked trade off between dilation and expansion. For the n dimensional star network we exhibit: (1) a dilation N-1 embedding of S/sub n/ into H/sub n/, where N=[log/sub 2/(n!)]; (2) a dilation 2(d+1) embedding of S/sub n/ into H/sub 2d+n-1/ where d=[log/sub 2/([n/2]!)]; (3) a dilation 2d+2i embedding of S(2/sup i/m) into H(2/sup i/d+i2/sup i/m-2i+1) where d=[log/sub 2/(m!)]; (4) a dilation L embedding of S/sub n/ into H/sub d/, where L=1+[log/sub 2/(n!)], and d=(n-1)L; (5) a dilation (k+1)(k+2)/2 embedding of S/sub n/ into H(n(k+1)-2/sup k+1/+1) where k=[log/sub 2/(n-1)]; (6) a dilation 3 embedding of S/sub 2k+1/ into H(2k/sup 2/+k); and (7) a dilation 4 embedding of S/sub 3k+2/ into H(3k/sup 2/+3k+1). Some of the embeddings are in fact optimum, in both dilation and expansion for small values of n. We also show that the embedding of S/sub n/ into its optimum hypercube requires dilation /spl Omega/(log/sub 2/ n).