The bicube: an interconnection of two hypercubes

Abstract

We consider two definitions of the even-dimensional hypercube given in the literature. The labelled graphs obtained by two definitions are not same, but one is isomorphic to the other. By interconnecting two labelled graphs in such a way that each pair of vertices with the same label are joined by an edge, we construct a vertex-symmetric graph with the diameter about half that of a comparable hypercube. We extend the result to a general scheme for interconnecting two hypercubes to produce a network topology called the bicube. We show that the bicube preserves the vertex-symmetry, bipartiteness, hamiltonian and bipancyclic properties of the hypercube, and is highly edge-symmetric.

Keywords:

• interconnection networks
• hypercubes
• diameter
• vertex-symmetry
• edge-symmetry

2010 AMS Subject Classifications::

• 05C90
• 68M10
• 68R10

Acknowledgement

This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2013R1A1A2012890).