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

Graph Embedding Aspect of IEH Graphs

**Hung-Yi Chang and Rong-Jaye Chen**

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 (**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.