On graph irregularity strength

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)less than or equal toc(1) n/epsilon, for graphs with maximum degree Deltaless than or equal ton(1/ 2) and minimum degree delta, and s(G)less than or equal toc(2) (log n)n/delta, for graphs with Delta>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. (C) 2002 Wiley Periodicals, Inc.