An isometric embedding of a connected graph G into a cartesian product
of complete graphs is equivalent to a labeling of each vertex of G by
a string of fixed length such that the distance in G between two vert
ices is equal to the Hamming distance between their labels. We give a
simple O(D(m, n) + n2)-time algorithm for deciding if G admits such an
embedding, and for labeling G if one exists, where D(m, n) is the tim
e needed to compute the all-pairs distance matrix of a graph with m ed
ges and n vertices. If the distance matrix is part of the input, our a
lgorithm runs in O(n2) time. We also show that an n-vertex subgraph of
(K(a))d, the cartesian product of d cliques of size a, cannot have mo
re than 1/2(a - 1)n log(a) n edges. With this result our algorithm can
be used to decide whether a graph G is an a-ary Hamming graph in O(n2
log n) time (for fixed a).