On the gracesize of trees
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915618645606400 |
|---|---|
| author | Letzter, Shoham Pokrovskiy, Alexey Williams, Ella |
| author_facet | Letzter, Shoham Pokrovskiy, Alexey Williams, Ella |
| contents | An $n$-vertex tree $T$ is said to be $\textit{graceful}$ if there exists a bijective labelling $ϕ:V(T)\to \{1,\ldots,n\}$ such that the edge-differences $\{|ϕ(x)-ϕ(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 $\textit{gracesize}$ of an $n$-vertex tree $T$, denoted $\operatorname{gs}(T)$, is the maximum possible number of distinct edge-differences over all bijective labellings $ϕ:V(T)\to \{1,\ldots,n\}$. The graceful tree conjecture is therefore equivalent to the statement that $\operatorname{gs}(T)=n-1$ for all $n$-vertex trees.
We prove an asymptotic version of this conjecture by showing that for every $\varepsilon>0$, there exists $n_0$ such that every tree on $n>n_0$ vertices satisfies $\operatorname{gs}(T)\geqslant (1-\varepsilon)n$. In other words, every sufficiently large tree admits an almost graceful labelling. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_11331 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the gracesize of trees Letzter, Shoham Pokrovskiy, Alexey Williams, Ella Combinatorics An $n$-vertex tree $T$ is said to be $\textit{graceful}$ if there exists a bijective labelling $ϕ:V(T)\to \{1,\ldots,n\}$ such that the edge-differences $\{|ϕ(x)-ϕ(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 $\textit{gracesize}$ of an $n$-vertex tree $T$, denoted $\operatorname{gs}(T)$, is the maximum possible number of distinct edge-differences over all bijective labellings $ϕ:V(T)\to \{1,\ldots,n\}$. The graceful tree conjecture is therefore equivalent to the statement that $\operatorname{gs}(T)=n-1$ for all $n$-vertex trees. We prove an asymptotic version of this conjecture by showing that for every $\varepsilon>0$, there exists $n_0$ such that every tree on $n>n_0$ vertices satisfies $\operatorname{gs}(T)\geqslant (1-\varepsilon)n$. In other words, every sufficiently large tree admits an almost graceful labelling. |
| title | On the gracesize of trees |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2511.11331 |