Dilation d embedding of a hyper-pyramid into a hypercube
C. T. Howard Ho, S. Lennart Johnsson · 1989
A P(k, d) hyper-pyramid 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 dimensional Boolean subcube at level i, except for the leaf level k. Hyper-pyramids contain pyramids as proper subgraphs. We show that a P(k, d) hyper-pyramid can be embedded in a Boolean cube with minimal expansion and dilation d. The congestion is bounded from above by 2d+1/d+2 and from below by 1 + ⌈2d-d/kd+1⌉. For P(k, 2) hyper-pyramids we present a dilation 2 and congestion 2 embedding. As a corollary a complete n-ary tree can be embedded in a Boolean cube with dilation max(2, ⌈log2 n⌉) and expansion 2k⌈log2 n⌉ + 1/nk+1-1/n-1. We also discuss multiple pyramid embeddings.