Irregular Assignments of Trees and Forests
Martin Aigner, E. Triesch · SIAM Journal on Discrete Mathematics · 1990
Let G be a graph on n vertices. An irregular assignment of G is a weighting $ w:E ( G ) \to \{ 1, \cdots ,m \} $ of the edge-set of G such that all weighted degrees $w( v ) = \sum_{v \in e} w ( e ) $ are distinct. The minimal number m for which this is possible is called the irregularity strength$s( G )$ of G. Lehel and others have shown that $s ( G ) < \infty $ implies $s ( G )\leqq n- 1$ for connected graphs on $n \geqq 4$ vertices, and $s( G )\leqq 2n - 3$ for arbitrary graphs. By using decompositions of the additive group $\mathbf{Z}_r $ (integers mod r), these results are strengthened. Main Theorem: $s ( G )\leqq n + 1$ for any graph with $s( G ) < \infty $.