FASTER ISOMETRIC EMBEDDING IN PRODUCTS OF COMPLETE GRAPHS

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).