Cartesian products of graphs as spanning subgraphs of de Bruijn graphs

For Cartesian products G=G₁×⋯× G _m (m≥2) of nontrivial connected graphs G _i and the n-dimensional base B de Bruijn graph D=D _B (n), we investigate whether or not there exists a spanning subgraph of D which is isomorphic to G. We show that G is never a spanning subgraph of D when n is greater than three or when n equals three and m is greater than two. For n=3 and m=2, we can show for wide classes of graphs that G cannot be a spanning subgraph of D. In particular, these non-existence results imply that D _B (n) never contains a torus (i.e., the Cartesian product of m≥2 cycles) as a spanning subgraph when n is greater than two. For n=2 the situation is quite different: we present a sufficient condition for a Cartesian product G to be a spanning subgraph of D=D _B (2). As one of the corollaries we obtain that a torus G=G₁×⋯× G _m is a spanning subgraph of D=D _B (2) provided that ∥G∥=∥D∥ and that the G _i are even cycles of length ≥4. In addition we apply our results to obtain embeddings of relatively small dilation of popular processor networks (as tori, meshes and hypercubes) into de Bruijn graphs of fixed small base.