Graham–Sloane harmonious labeling conjecture

From papers

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.

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

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.

Solutions 0

No solutions have been posted yet.