JISE


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


Journal of Information Science and Engineering, Vol. 17 No. 1, pp. 22-33


Graph Embedding Aspect of IEH Graphs


Hung-Yi Chang and Rong-Jaye Chen
Department of Computer Science and Information Engineering 
National Chiao Tung University 
Hsinchu, Taiwan 300, R.O.C. 
E-mail: leorean@csie.nctu.edu.tw


    In order to overcome the drawback of the hypercube that the number of nodes is limited to a power of two, the incrementally extensible hypercube (IEH) graph is derived for an arbitrary number of nodes [12]. In this paper, we first prove that the incomplete hypercube (IH) is a spanning subgraph of IEH. Next, we present a new method to construct an IEH from an IH. From the aspect of graph embedding, we determine the minimum size of the IEH that contains a complete binary tree. We then embed a torus (with a side length as power of two) into an IEH with dilation 1 and expansion 1.


Keywords: hypercubes, embedding, binary trees, meshes, incrementally extensible hypercubes, interconnection networks

  Retrieve PDF document (JISE_200101_02.pdf)