# Graph labeling and its degree

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?

• Must the labels $\ell_1, \dots, \ell_n$ be in the set $1, 2, \dots, n$? – Misha Lavrov Jan 25 at 21:05
• No, I'm considering $\ell_i\in \mathbb{Z}$. – sam wolfe Jan 25 at 21:17

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).$$
• What is the set $E$? – sam wolfe Jan 25 at 22:57