Irregularity Strength of Regular Graphs - Przybyło, Jakub (The Electronic Journal of Combinatorics, 2008)
Let G be a simple graph with no isolated edges and at most one isolated vertex. For a positive integer w, a w-weighting of G is a map f:E(G)→ {1,2,…,w}. An irregularity strength of G, s(G), is the smallest w such that there is a w-weighting of G for which _e:uef(e) eq_e:vef(e) for all pairs of different vertices u,vV(G). A conjecture by Faudree and Lehel says that there is a constant c such that s(G)nd+c for each d-regular graph G, d2. We show that s(G) < 16nd+6. Consequently, we improve the results by Frieze, Gould, Karoński and Pfender (in some cases by a n factor) in this area, as well as the recent result by Cuckler and Lazebnik.