Integer sets with prescribed pairwise differences being distinct

We label the vertices of a given graph G with positive integers so that the pairwise differences over its edges are all distinct. Let D(G) be the smallest value that the largest label can have. ample, for the complete graph Kn, the labels must form a Sidon set. Hence, D(Kn)=(1+o(1))n2. Rather surprisingly, we demonstrate that there are graphs with only n32+o(1) edges achieving this bound. enerally, we study the maximum value of D(G) that a graph G of the given order n and size m can have. We obtain bounds which are sharp up to a logarithmic multiplicative factor. The analogous problem for pairwise sums is considered as well. Our results, in particular, disprove a conjecture of Wood.