A note on embeddings among folded hypercubes, even graphs and odd graphs

Abstract

In this short note, we establish topological relationships among the folded hypercube FQ _n , the even graph E _k and the odd graphs O _d via embedding. Such embeddings are measured via dilation.

Keywords:

• interconnection network
• folded hypercube
• even graph
• odd graph
• embedding

2010 AMS Subject Classifications :

• 05C60
• 05C90

Acknowledgements

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

Notes

^†A preliminary an abridged version of this paper was presented by Hyeong-Ok Lee at The 2008 International Conference on Parallel Distributed Processing Techniques Applications.

The Hamming distance of two binary strings of the same length is the number of bits by which they differ.

The diameter of a graph is the maximum of the length of a shortest path between u and v, computed over all pairs of vertices u and v.

Throughout this note, we use the usual notation of s ₁ s ₂ to denote the concatenation of the two binary strings s ₁ and s ₂.