On the Graham--Sloane harmonious labelling conjecture
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915534602240000 |
|---|---|
| author | Müyesser, Alp Pokrovskiy, Alexey |
| author_facet | Müyesser, Alp Pokrovskiy, Alexey |
| contents | Consider an order $n$ abelian group $G$ and a tree $T$ on $n$ vertices. When is it possible to (bijectively) label $V(T)$ by $G$ so that along all edges $xy$ of $T$, the sums $x+y$ are distinct? This problem can be traced back to the work of Graham and Sloane on the harmonious labelling conjecture, and has been studied extensively since its introduction in 1980. We give a precise characterisation that holds for all bounded degree trees. In particular, our characterisation implies that if $G=\mathbb{Z}/n\mathbb{Z}$ and $T$ is a bounded degree tree, the desired labelling exists. This confirms a conjecture of Graham and Sloane from 1980, and another conjecture of Chang, Hsu, and Rogers from 1987, for bounded degree trees. Our results also have further applications for the study of graph coverings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_05280 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Graham--Sloane harmonious labelling conjecture Müyesser, Alp Pokrovskiy, Alexey Combinatorics Group Theory 05D15, 05D40, 20K01 Consider an order $n$ abelian group $G$ and a tree $T$ on $n$ vertices. When is it possible to (bijectively) label $V(T)$ by $G$ so that along all edges $xy$ of $T$, the sums $x+y$ are distinct? This problem can be traced back to the work of Graham and Sloane on the harmonious labelling conjecture, and has been studied extensively since its introduction in 1980. We give a precise characterisation that holds for all bounded degree trees. In particular, our characterisation implies that if $G=\mathbb{Z}/n\mathbb{Z}$ and $T$ is a bounded degree tree, the desired labelling exists. This confirms a conjecture of Graham and Sloane from 1980, and another conjecture of Chang, Hsu, and Rogers from 1987, for bounded degree trees. Our results also have further applications for the study of graph coverings. |
| title | On the Graham--Sloane harmonious labelling conjecture |
| topic | Combinatorics Group Theory 05D15, 05D40, 20K01 |
| url | https://arxiv.org/abs/2509.05280 |