# polytime transformation from a graph to a set of binary strings

$d_H$ denotes the Hamming distance between two binary strings of the same size. The problem is stated as follows. Given any undirected graph $(V, A)$, does there always exist a one-to-one correspondence $f : V \mapsto \Omega$, $f$ computable in polynomial time, where $\Omega$ is a set of binary strings of the same size and such that $\exists \alpha > 0$, $\forall v_i, v_j \in V$, $$d_H(f(v_i), f(v_j)) = \left\lbrace\begin{array}{ll} \alpha & \mbox{ if } (v_i, v_j) \in A,\\ \mbox{some value strictly greater than \alpha,}& \mbox{otherwise.} \end{array}\right.$$

For instance, if $(V, A)$ is a clique of size $3$, i.e., $V = \{v_1, v_2, v_3\}$ and $A = V \times V$, then such a function $f$ can be defined as follows: $f(v_1) = 100$, $f(v_2) = 010$, $f(v_3) = 001$. We have $d_H(v_1, v_2) = d_H(v_2, v_3) = d_H(v_1, v_3) = 2$.

As another example, consider a line $(V, A)$ of size $3$, i.e., $V = \{v_1, v_2, v_3\}$ and $A = \{(v_1, v_2), (v_2, v_1), (v_2, v_3), (v_3, v_2)\}$, then such a function $f$ can be defined as follows: $f(v_1) = 00$, $f(v_2) = 10$, $f(v_3) = 11$. We have $d_H(v_1, v_2) = d_H(v_2, v_3) = 1$ and $d_H(v_1, v_3) = 2$.

Yes. If the graph is regular there is a trivial scheme. Fix some ordering of the edges, and define $f(v)$ to be $0$ at the corresponding position of a particular edge if $v$ is not incident to that edge, and $1$ is $v$ is incident to the edge.
If the graph is $k$-regular, then $d_H(f(v),f(u))$ is $2k-2$ if $u$ and $v$ are adjacent, and $2k$ if they are not.
If the graph is not regular, then we may pad the graph with additional degree $1$ vertices such that all of the original vertices have the same degree. Then the above scheme will work.
• In your proposal, don't we rather get $d_H(f(v), f(u)) = 2k-2$ if $u$ and $v$ are adjacent, $2k$ otherwise? May you please confirm it? Well, this would work still work but I need to make sure of that. About your last sentence on the general case, then a modification of the graph seems necessary (adding a vertex), which I cannot allow. Overall, it is fine for the problem I am interested in to restrict the input graph to a cubic one, so everything would be fine for me. Jan 18, 2015 at 13:36
• You are right about the $2k$ v.s. $k$ thing. With regards to modifying the graph in the general case, you don't need to actually modify the graph, you just need to define $f$ as if these additional vertices existed, but can forget that these vertices exist afterwards. All you are doing is padding the resulting string with extra $0$'s and $1$'s so that $f(v)$ always has the same number of $1$'s (namely, equal to the maximum degree of the graph). Jan 18, 2015 at 14:26