Embedding hypercubes, rings, and odd graphs into hyper-stars

Abstract

Hypercubes and star graphs are two of the most fundamental classes of interconnection networks. The class of hyper-stars was introduced as a hybrid of these two classes. In this note, we establish topological relationship between the hyper-stars and three known classes of networks, namely, hypercubes, tori and odd graphs, via embedding.

Keywords:

• hypercube
• torus
• hyper-star
• odd graph
• embedding

AMS Subject Classifications :

• 68M10
• 90B18

Acknowledgements

We are grateful to the two anonymous referees for their helpful comments and suggestions.

Notes

^†Although the traditional definition for tori is over the set {0, 1, 2, …, n−1}, our equivalent definition is more natural in the bijection given in Theorem 3.1.