Dilation d embedding of a hyper-pyramid into a hypercube

Abstract

A P(k,d) hyperpyramid is a level structure of k Boolean cubes where the cube at level i is of dimension id, and a node at level i - 1 connects to every node in a d dimension Boolean subcube at level i, except for the leaf level k. Hyperpyramids contain pyramids as proper subgraphs. It is shown that a P(k,d) hyperpyramid can be embedded in a Boolean cube with minimal expansion and dilation d. For P(d, 2) hyperpyramids a dilation 2 and congestion 2 embedding is presented. The embeddings can be used to improve the congestion to 3 for the embedding of one k level pyramid and two k - 1 level pyramids. An expansion of approximately one can also be obtained for hyperpyramids by embedding 2d - 2 hyperpyramids of height k - 1 with a hyperpyramid of height k.