Graham--Sloane harmonious tree conjecture

About 10 years old · traced to

Let TT be a tree with nn vertices. A harmonious labelling assigns distinct vertex labels and gives an edge uvuv the label (ψ(u)+ψ(v)) mod (n−1)(\psi(u)+\psi(v))\bmod(n-1). Harmonious Tree Conjecture. For any nn-vertex tree TT there exists an injective labelling

ψ:V(T)→[n]\psi:V(T) \rightarrow [n]

such that the values

(ψ(u)+ψ(v)mod  (n−1))uv∈E(T)\Big(\psi(u)+\psi(v)\mod (n-1)\Big)_{uv\in E(T)}

are pairwise distinct. This is the harmonious analogue of the graceful tree conjecture, introduced by Graham and Sloane; the source gives no resolution and the problem remains open.

References

Primary source

Anna Adamaszek, Peter Allen, Codrut Grosu and Jan Hladky, “Almost all trees are almost graceful”, arXiv:1608.01577 (2019).

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.