Finding Antimagic Labelings of Trees by Evolutionary Search

Randomized search heuristics can sometimes be effective verifiers for combinatorial conjectures. In this paper, we demonstrate how a simple evolutionary algorithm can be used to confirm the antimagic tree conjecture for all trees up to order 25. This conjecture, which has been open for over thirty years, is that every tree except K2 has an antimagic labeling: a bijective edge labeling such that the sum of labels assigned to edges incident to a vertex v is unique for all vertices v μ V. Moreover, we formally prove that that simple evolutionary algorithms are guaranteed to find antimagic labelings in expected polynomial time on trees of any order for certain restricted classes (paths, combs, uniform caterpillars, uniform spiders and perfect binary trees).