On the gracesize of trees

Abstract

An $n$-vertex tree $T$ is said to be $\text{graceful}$ if there exists a bijective labelling $\ddot{I}•:V(T)\to \{1,\dots ,n\}$ such that the edge-differences $\{|\ddot{I}•(x)-\ddot{I}•(y)|:xy\in E(T)\}$ are pairwise distinct. The longstanding graceful tree conjecture, posed by Rósa in the 1960s, asserts that every tree is graceful. The $\text{graceful}$ of an $n$-vertex tree $T$, denoted $\mathrm{gs}(T)$, is the maximum possible number of distinct edge-differences over all bijective labellings $\ddot{I}•:V(T)\to \{1,\dots ,n\}$. The graceful tree conjecture is therefore equivalent to the statement that $\mathrm{gs}(T)=n-1$ for all $n$-vertex trees. We prove an asymptotic version of this conjecture by showing that for every $\epsilon >0$, there exists $n_0$ such that every tree on $n>n_0$ vertices satisfies $\mathrm{gs}(T)⩾(1-\epsilon )n$. In other words, every sufficiently large tree admits an almost graceful labelling.

23 pages, 6 figures