Short proof of the asymptotic confirmation of the Faudree-Lehel Conjecture

Abstract

Given a simple graph $G$, the {\it irregularity strength} of $G$, denoted $s(G)$, is the least positive integer $k$ such that there is a weight assignment on edges $f:E(G)\to \{1,2,\dots ,k\}$ for which each vertex weight $f^V(v):={\sum }_{u:\{u,v\}\in E(G)}f(\{u,v\})$ is unique amongst all $v\in V(G)$. In 1987, Faudree and Lehel conjectured that there is a constant $c$ such that $s(G)\le n/d+c$ for all $d$-regular graphs $G$ on $n$ vertices with $d>1$, whereas it is trivial that $s(G)\ge n/d$. In this short note we prove that the Faudree-Lehel Conjecture holds when $d\ge n^{0.8+\epsilon }$ for any fixed $\epsilon >0$, with a small additive constant $c=28$ for $d$ large enough. Furthermore, we confirm the conjecture asymptotically by proving that for any fixed $\beta \in (0,1/4)$ there is a constant $C$ such that for all $d$-regular graphs $G$, $s(G)\le \frac{n}{d}(1+\frac{C}{d^{\beta }})+28$, extending and improving a recent result of Przybyło that $s(G)\le \frac{n}{d}(1+\frac{1}{{\ln }^{\epsilon /19}n})$ whenever $d\in [{\ln }^{1+\epsilon }n,n/{\ln }^{\epsilon }n]$ and $d$ is large enough.

10 pages