Linear layout of locally twisted cubes

ABSTRACT

The hypercube network is one of the most popular parallel computing networks since it has a simple structure and is easy to implement. The locally twisted cube is a newly introduced variant of the hypercube which has the same number of nodes and same number of connections per node as the hypercube, but has only half the diameter and better graph embedding capability as compared to hypercube. In this paper, we show that an n-dimensional locally twisted cube is constructed by forming a matching between the nodes of two disjoint copies of an $(n-1)$-dimensional hypercube. In addition, we embed the locally twisted cube into path with minimum layout.

KEYWORDS:

• locally twisted cube
• embedding
• layout
• edge isoperimetric problem
• optimal order

2000 AMS Subject Classifications:

• 05C60
• 90B10
• 68M07

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work is supported by Project No. 5LCTOI14MAT002, Loyola College – Times of India, Chennai, India.