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

Journal of Inforamtion Science and Engineering, Vol.17 No.1, pp.23-33 (January 2001)

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.

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

Full Text () Retrieve PDF document (200101_02.pdf : 3,563,874 bytes)

Received March 25, 1998; revised May 11 & July 6, 1998; accepted July 27, 1998.
Communicated by Wen-Lian Hsu.