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 $\sum_{e:u\in e}f(e) eq\sum_{e:v\in e}f(e)$ for all pairs of different vertices $u,v\in V(G)$. A conjecture by Faudree and Lehel says that there is a constant $c$ such that $s(G)\le{n\over d}+c$ for each $d$-regular graph $G$, $d\ge 2$. We show that $s(G) < 16{n\over d}+6$. Consequently, we improve the results by Frieze, Gould, Karoński and Pfender (in some cases by a $\log n$ factor) in this area, as well as the recent result by Cuckler and Lazebnik.