Almost graceful tree conjecture

Question

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

Answer 1

I know no reference, but here is an easy way of achieving $|D|\geq\lceil n/2\rceil$ (for $n\geq 2$, surely).

The vertices of every tree can be decomposed into stars (i.e., graphs of te form $K_{1,d}$ with $d\geq 1$): if a tree is not a star, merely find a non-leaf vertex having just one non-leaf neighbor and single out this vertex with all its leaves; then proceed by induction.

Now, given such star decomposition, we assign to the vertices some $n$ consecutive integers (this suffices due to shift-invariance) in the following way. Take the stars in turn; for every star, assign the largest unassigned negative integer to its center, and the smallest unassigned nonnegative integers to the other vertices. This way, all stars' edges get different labels, and there are at least $\lceil n/2\rceil$ of them.

Remarks. There are some improvements of the algorithm, but they seem to add $o(n)$. E.g.,one may choose a `path of stars' and make the labels of the edges of this path also distinct from each other and from the labels of stars' edges. Alternatively, each star can be equipped with one additional path starting from a non-central vertex:

Answer 2

For the class of trees with maximum degree $o(n/\log n)$, https://arxiv.org/abs/1608.01577 shows that we can achieve a slightly different version of 'almost graceful': if $T$ has not $n$ vertices but only $(1-o(1))n$, we can have an injective $f$ such that your set $D$ has size $|E(T)|$.

It follows that for $n$-vertex trees with maximum degree $o(n/\log n)$ we can have $|D|=(1-o(1))n$. To see this, remove $o(n)$ leaves, use the AAGH result to label the remaining tree, and then replace the leaves, labelling them in any way which completes $f$ to a bijection. This might fail to add any new entries to $D$, but it was already big enough for the claim.