Contents

Heuristic Algorithms for Finding Irregularity Strengths of Graphs

David K. Garnick1, Jeffrey H. Dinitz2
1Department of Computer Science Bowdoin College, Brunswick, ME USA 04011
2Department of Mathematics University of Vermont, Burlington, VT USA 05405

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 \({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.