The harmonious labelling conjecture

About 1 year old · traced to

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 xy∈E(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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.