<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-01-18T13:36:28.650Z
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.
user109711
CC BY-SA 3.0
2015-01-18T14:26:00.180Z
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).
Tom van der Zanden
CC BY-SA 3.0
2015-01-18T11:24:24.197Z
2015-01-18T14:22:27.597Z
2015-01-18T14:22:27.597Z
Tom van der Zanden
<p>$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 &gt; 0$, $\forall v_i, v_j \in V$,
$$d_H(f(v_i), f(v_j)) = \left\lbrace\begin{array}{ll}
\alpha &amp; \mbox{ if } (v_i, v_j) \in A,\\
\mbox{some value strictly greater than $\alpha$,}&amp; \mbox{otherwise.}
\end{array}\right.$$</p>

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

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

<cc.complexity-theory><graph-theory><graph-algorithms><polynomial-time><string-matching>
polytime transformation from a graph to a set of binary strings
user109711
# polytime transformation from a graph to a set of binary strings

(Asked by: username_0 on 2015-01-18)

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

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, polynomial-time, string-matching


---

## 1 answers

### Answer by username_1 on 2015-01-18. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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).  

---

