Graham–Sloane harmonious labeling conjecture

About 15 years old · traced to

Let GG be a graph with mm edges and at most mm vertices. A labeling f:V(G)→Zmf:V(G)\to\mathbb{Z}_m is harmonious when the edge labels f′(xy)=f(x)+f(y)f'(xy)=f(x)+f(y) are all distinct; for a tree on nn vertices, every label is required to be used on some vertex.

Graham–Sloane conjecture. Every tree is harmonious.

The source notes that almost all graphs are not harmonious, while a later theorem shows that every tree has an injective harmonious labeling using an Abelian group of order n+o(n)n+o(n). The exact conjecture remains unresolved in the supplied text.

References

Primary source

Benny Sudakov, “Restricted subgraphs of edge-colored graphs and applications”, arXiv:2412.13945 (2024).

Additional references

3 papers in this index state this conjecture (2011–2024). The statement above is taken from the most recent of them; the others are arXiv:1803.03316, arXiv:1106.3490.

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.