Shun-Shan Tsai and Shi-Jinn Horng
Department of Electrical Engineering
National Taiwan Institute of Technology
Taipei, Taiwan 107, R.O.C.
Recently, a generalized graph, the arrangement graph, has been proposed to solve some problems of star graphs. It is claimed to be more economic than star graphs considering the number of nodes, and is used to embed hypercubes  with unit dilation and expansion or with dilation 3 and expansion . Based on the previous results the expansion of such an embedding will increase exponentially. Hence, it is rather impractical. In this paper, a different embedding strategy is proposed to reduce the high expansion when embedding hypercubes in arrangement graphs; this can be done with unit dilation and unit expansion.
Keywords: star graphs, arrangement graphs, hypercube
Received June 24, 1995; revised April 23, 1996.
Communicated by Wei-Pang Yang.
*This work was supported by National Science Council under the contract No. NSC-84-0404-E-011-014.