The harmonious labelling conjecture

From papers

Let TT be a tree with nn edges, and let Zn\mathbb{Z}_n denote the cyclic group of order nn. A labelling is a map ϕ ⁣:V(T)Zn\phi\colon V(T)\to \mathbb{Z}_n; edge sums are the values ϕ(x)+ϕ(y)\phi(x)+\phi(y) for xyE(T)xy\in E(T).

The harmonious labelling conjecture. For every nn-edge tree TT, there exists a labelling ϕ ⁣:V(T)Zn\phi\colon V(T)\to \mathbb{Z}_n such that the edge sums ϕ(x)+ϕ(y)\phi(x)+\phi(y) are all distinct, and exactly one label is used on two vertices.

This is the cyclic additive labelling conjecture of Graham and Sloane. The paper states that it is confirmed for bounded-degree trees, but the unrestricted conjecture remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Alp Müyesser and Alexey Pokrovskiy, “On the Graham–Sloane harmonious labelling conjecture”, arXiv:2509.05280 (2025).

Solutions 0

No solutions have been posted yet.