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 _n into H_n, where N=[log₂(n!)]; (2) a dilation 2(d+1) embedding of S_n into H_2d+n-1 where d=[log₂([n/2]!)]; (3) a dilation 2d+2i embedding of S(2ⁱ m) into H(2ⁱd+i2ⁱm-2i+1) where d=[log₂ (m!)]; (4) a dilation L embedding of S_n into H_d , where L=1+[log₂(n!)], and d=(n-1)L; (5) a dilation (k+1)(k+2)/2 embedding of S_n into H(n(k+1)-2^k+1+1) where k=[log₂(n-1)]; (6) a dilation 3 embedding of S_2k+1 into H(2k²+k); and (7) a dilation 4 embedding of S_3k+2 into H(3k²+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_n into its optimum hypercube requires dilation Ω(log₂ n)