Consider any graph with $n$ vertices, arbitrary size and no loops. Take a random labeling $i=1,...,n$ of the vertices. Is there a way of relabeling the graph such that, for any vertex $i$, with corresponding new label $\ell_i\in\mathbb{Z}$, there exists a set $L$ for which $$ \deg(i)=\sum_{j=1}^n \textbf{1}_L(\ell_i-\ell_j) $$ yields the degree of vertex $i$? Here, $\textbf{1}_L$ is the indicator function on the set $L$.
For example, in the cycle case, with $\ell_i=i$, the set $L=\{\ell\,:\,|\ell|\equiv 1 \mod (n-2)\}$ seems to do the trick, that is, $\deg(i)=2, \forall i$. Any ideas regarding a general graph?
The most straightforward thing to do is take the labels $\ell_1, \dots, \ell_n$ to be so far apart that no difference $\ell_i - \ell_j$ is repeated.
This is achieved by any Sidon sequence, and the densest ones with $n$ elements would have labels going up to about $n^2$ or so. If we don't care for optimizing, then we can take $\ell_i = 2^i$; if $2^a - 2^b = 2^c - 2^d$, then we also have $2^a + 2^d = 2^b + 2^c$, and by the uniqueness of binary representations, we must have $a=c$ and $b=d$.
Now just let $L = \{2^i - 2^j : ij \in E\}$, where $E$ is the edge set of the graph. This leads to $$ \sum_{j=1}^n \mathbf1_L(\ell_i -\ell_j) = \sum_{j=1}^n \mathbf1_E(ij) = \deg(i). $$