EMBEDDINGS OF HYPERCUBES AND GRIDS INTO DE BRUIJN GRAPHS

An embedding of a graph G into a graph H is an injective mapping f from the vertices of G into the vertices of H together with a mapping P-f of edges of G into paths in H. The dilation of the embedding is tile maximum taken over all the lengths of the paths P-f(xy) associated with the edges xy of G. We show that it is possible to embed a D-dimensional hypercube into the binary de Bruijn graph of the same order and diameter with dilation at most [D/2]. Similarly a majority of planar grids can be embedded into a binary de Bruijn graph of the same or nearly the same order with dilation at most [D/2] where D is the diameter of the de Bruijn graph. (C) 1994 Academic Press, Inc.