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

| cite | improve this answer | |
  • $\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 '15 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$ – Tom van der Zanden Jan 18 '15 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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