1
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ What is the set $E$? $\endgroup$ – sam wolfe Jan 25 at 22:57
  • $\begingroup$ The edge set of the graph. $\endgroup$ – Misha Lavrov Jan 25 at 22:57
  • $\begingroup$ Thank you, it's very clear now! Interesting concept this of Sidon sequence. $\endgroup$ – sam wolfe Jan 25 at 23:15

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.