EMBEDDING GRAPHS ONTO THE SUPERCUBE

In this paper we consider the Supercube, a new interconnection network derived from the Hypercube. The Supercube, introduced by sen in [10], has the same diameter and connectivity as a Hypercube but can be real ized for any number of nodes, not only powers of 2. We study the Super cube's ability to execute parallel programs, using graph-embedding tec hniques. We show that complete binary trees and bidimensional meshes ( with a side length power of 2) are spanning subgraphs of the Supercube . We then prove that the Supercube is Hamiltonian and, when the number of nodes is not a power of 2, it contains all cycles of length greate r than 3 as subgraphs.