\(\ell_ 1\)-rigid graphs (Q1321589)

An \(\ell_ 1\)-graph is a graph whose vertices can be labelled by binary vectors in such a way that the distance between any two vertices in the graph coincides, up to scale, with the Hamming distance between their binary addresses. The \(\ell_ 1\)-graphs have been characterized by \textit{S. V. Shpectorov} [Eur. J. Comb. 14, No. 2, 117-130 (1993; Zbl 0773.05044)] and the first author and \textit{P. Grishukhin} [Q. J. Math., Oxf. II. Ser. 44, No. 176, 399-433 (1993; Zbl 0795.05120)]. In this paper, the authors demonstrate that many interesting graphs are in fact \(\ell_ 1\)-rigid, i.e., they admit essentially a unique binary labelling. They show that \(\ell_ 1\)-rigid graphs include, e.g., all bipartite \(\ell_ 1\)-graphs, most half-cubes and Johnson graphs, and others.