Embedding of special classes of circulant networks, hypercubes and generalized Petersen graphs

Abstract

Hypercubes are a very popular model for parallel computation because of their regularity and the relatively small number of interprocessor connections. In this paper, we present an algorithm for embedding special class of circulant networks into their optimal hypercubes with dilation 2 and prove its correctness. Also, we embed special class of circulant networks into special class of generalized Petersen graphs with dilation 2 and vice versa.

Keywords:

• generalized Petersen graph
• hypercube
• circulant network
• embedding
• dilation

2010 AMS Subject Classifications::

• 05C12
• 05C85
• 68M10

Acknowledgements

We are greatly indebted to the referees whose valuable criticisms and suggestions led us to make changes in the paper. Also, we thank S. Sudeep and G. Cyriac, Postgraduate students of the Department of Mathematics, Loyola College, Chennai, India, for their help. This work is supported by DST Project No. SR/S4/MS: 494/07, New Delhi, India.

Additional information

Notes on contributors

Indra Rajasingh

Current affiliation: School of Advanced Sciences, VIT University, Chennai – 600 048, India