Heuristic Algorithms for Finding Irregularity Strengths of Graphs

Abstract

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 $irregularitystrength$ 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.