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


1 Answer 1


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.

  • $\begingroup$ 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. $\endgroup$
    – user109711
    Jan 18, 2015 at 13:36
  • 1
    $\begingroup$ 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). $\endgroup$ Jan 18, 2015 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.