On graph irregularity strength

Abstract

Abstract An assignment of positive integer weights to the edges of a simple graph G is called irregular, if the weighted degrees of the vertices are all different. The irregularity strength, s ( G ), is the maximal weight, minimized over all irregular assignments. In this study, we show that s ( G ) ≤ c 1 n /δ, for graphs with maximum degree Δ ≤ n 1/2 and minimum degree δ, and s ( G ) ≤ c 2 (log n ) n /δ, for graphs with Δ > n 1/2 , where c 1 and c 2 are explicit constants. To prove the result, we are using a combination of deterministic and probabilistic techniques. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 120–137, 2002