Irregularity strength of regular graphs (Q1010805)

Summary: 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)\rightarrow \{1,2,\dots,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)\neq\sum_{e:v\in e}f(e)\) for all pairs of different vertices \(u,v\in V(G)\). A conjecture by \textit{R.J. Faudree} and \textit{J. Lehel} [Combinatorics, Proc. 7th Hung. Colloq., Eger/Hung. 1987, Colloq. Math. Soc. János Bolyai 52, 247-256 (1988; Zbl 0697.05048)] says that there is a constant \(c\) such that \(s(G)\leq\frac{n}{d}+c\) for each \(d\)-regular graph \(G, d\geq 2\). We show that \(s(G)< 16\frac{n}{d}+6\). Consequently, we improve the results by \textit{A. Frieze}, \textit{R.J. Gould}, \textit{M. Karoński}, and \textit{F. Pfender} [J. Graph Theory 41, No.\,2, 120--137 (2002; Zbl 1016.05045)] (in some cases by a \(\log n\) factor) in this area, as well as the recent result by \textit{B. Cuckler} and \textit{F. Lazebnik} [J. Graph Theory 58, No.\,4, 299--313 (2008; Zbl 1188.05112)].