The graceful tree conjecture is the following statement: for any tree $T = (V, E)$ with $|V| = n$ there is a bijective map $f: V \to [n]$ such that $D = \{|f(x) - f(y)| \mid xy \in E\} = [n - 1]$.

There are some positive results about narrow classes of trees, as well as computational results for small $n$ (the best I could find is positive for all $n \leq 35$). One could, however, ask for unconditional results about largest $|D|$ achievable for all trees with a given $n$. An easy greedy algorithm yields $|D|$ of size $n / 3$ for any tree of size $n$. Are there better results, for instance with $|D| \geq cn$ for $c > 1/3$, or even $|D| \geq n - o(n)$?