Graph embedding aspect of IEH graphs

H. Y. Chang*, Rong-Jaye Chen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)23-33
Number of pages11
JournalJournal of Information Science and Engineering
Volume17
Issue number1
StatePublished - 1 Jan 2001

Keywords

  • Binary trees
  • Embedding
  • Hypercubes
  • Incrementally extensible hypercubes
  • Interconnection networks
  • Meshes

Fingerprint Dive into the research topics of 'Graph embedding aspect of IEH graphs'. Together they form a unique fingerprint.

Cite this