**F. Aurenhammer, M. Formann, R. Idury, A. Schaeffer, and F. Wagner**

An isometric embedding of a connected graph into a cartesian product of
complete graphs is equivalent to a labeling of each vertex of by a string
of fixed length such that the distance in between two vertices is equal
to the Hamming distance between their labels. We give a simple
-time algorithm for deciding if admits such an
embedding, and for labeling if one exists, where is the time
needed to compute the all-pairs distance matrix of a graph with edges and
vertices. If the distance matrix is part of the input, our algorithm runs
in time. We also show that an -vertex subgraph of
, the cartesian product of equal-sized complete graphs,
cannot have more than
edges. With this result our
algorithm can be used to decide whether a graph is an -ary Hamming
graph in time (for fixed ).