A note on \(l_ 1\)-rigid planar graphs (Q1911837)

Let \(p_1,\dots, p_k\) be positive integers and let \(n= p_1+\cdots+ p_k\). Let \(G\) be the graph obtained from the \(n\)-cycle with vertices \(1,\dots, n\) by adding a new vertex adjacent to \(p_1, p_1+ p_2,\dots, p_1+\cdots+ p_k\). It is characterized for which parameters \(p_1,\dots, p_k\), the graph \(G\) has an \(\ell_1\)-embedding into some hypercube, i.e., there are numbers \(\lambda\) and \(q\) and a mapping \(\phi: V(G)\to \{0, 1\}^q\) such that for any two vertices \(u, v\in V(G)\), the distance from \(u\) to \(v\) in \(G\) is equal to the product of \(\lambda\) and the Hamming distance between \(\phi(u)\) and \(\phi(v)\). It is also shown that the mapping \(\phi\), whenever it exists, is essentially unique with the only exception being the graph \(K_4\) whose parameters are \(p_1= p_2= p_3= 1\).