Recognizing binary Hamming graphs in $O(n^{2} \log n)$ time

F. Aurenhammer and J. Hagauer


A graph $G$ is called a binary Hamming graph if each vertex of $G$ can be assigned a binary address of fixed length such that the Hamming distance between two addresses equals the length of a shortest path between the corresponding vertices. It is shown that $O(n^2 \log n)$ time suffices for deciding whether a given $n$-vertex graph $G$ is a binary Hamming graph, and for computing a valid addressing scheme for $G$ provided its existence. This is not far from being optimal as $n$ addresses of length $n-1$ have to be computed in the worst case.

Reference: F. Aurenhammer and J. Hagauer. Recognizing binary Hamming graphs in $O(n^{2} \log n)$ time. In Proc. $16^{th}$ Int'l Workshop on Graph-Theoretical Concepts in Computer Science, Lecture Notes in Computer Science, volume 484, pages 90-98, Berlin, Germany, 1991. Springer Verlag.