Cartesian products of graphs as subgraphs of de Bruijn graphs of dimension at least three (Q1372727)

Given a Cartesian product of nontrivial connected graphs and a de Bruijn graph \(B(d,D)\) of base \(d\) and dimension \(D\), the paper studies the conditions under which the Cartesian product is a subgraph of \(B(d,D)\). It gives a complete solution to this problem for the case \(D\geq 4\). For \(D=3\) it gives partial results including a complete solution for the case that the Cartesian product is the product of cycles.