Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.12 No.4, pp.585-592 (December 1996)
Efficient Embedding Hypercube on
Arrangement Graphs*

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[1], 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 [2] with unit dilation and expansion JISE or with dilation 3 and expansion JISE. 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.