Heuristic Algorithms for Finding Irregularity Strengths of Graphs

Given a graph \(G\) with weighting \(w: E(G) \to Z^+\), the strength of \(G(w)\) is the maximum weight on any edge. The sum of a vertex in \(G(w)\) is the sum of the weights of all its incident edges. \(G(w)\) is \({irregular}\) if the vertex sums are distinct. The \({irregularity \; strength}\) of a graph is the minimum strength of the graph under all irregular weightings. We present fast heuristic algorithms, based on hill-climbing and simulated annealing, for finding irregular weightings of a given strength. The heuristics are compared empirically, and the algorithms are then used to formulate a conjecture.