JISE


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


Journal of Information Science and Engineering, Vol. 12 No. 4, pp. 585-592


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

  Retrieve PDF document (JISE_199604_06.pdf)