Recognizing Hamming graphs in linear time and space

Hamming graphs are, by definition, the Cartesian product of complete graphs. In the bipartite case these graphs are hypercubes. We present an algorithm recognizing Hamming graphs in linear time and space. This improves a previous algorithm which was linear in time but not in space. This also favorably compares to the general decomposition algorithms of graphs with respect to the Cartesian product, none of which is linear.