On the asymptotic confirmation of the Faudree-Lehel Conjecture for general graphs

Abstract

Given a simple graph $G$, the {\it irregularity strength} of $G$, denoted by $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\}$ attributing distinct weighted degrees: $\tilde{f}(v):={\sum }_{u:\{u,v\}\in E(G)}f(\{u,v\})$ to all vertices $v\in V(G)$. It is straightforward that $s(G)\ge n/d$ for every $d$-regular graph $G$ on $n$ vertices with $d>1$. In 1987, Faudree and Lehel conjectured in turn that there is an absolute constant $c$ such that $s(G)\le n/d+c$ for all such graphs. Even though the conjecture has remained open in almost all relevant cases, it is more generally believed that there exists a universal constant $c$ such that $s(G)\le n/\delta +c$ for every graph $G$ on $n$ vertices with minimum degree $\delta \ge 1$ which does not contain an isolated edge. In this paper we confirm that the generalized Faudree-Lehel Conjecture holds for graphs with $\delta \ge n^{\beta }$ where $\beta$ is any fixed constant larger than $0.8$. Furthermore, we confirm that the conjecture holds in general asymptotically. That is we prove that for any $\epsilon \in (0,0.25)$ there exist absolute constants $c_1,c_2$ such that for all graphs $G$ on $n$ vertices with minimum degree %at least $\delta \ge 1$ and without isolated edges, $s(G)\le \frac{n}{\delta }(1+\frac{c_1}{{\delta }^{\epsilon }})+c_2$, thus extending in various aspects and strengthening a recent result of Przybyło, who showed that $s(G)\le \frac{n}{d}(1+\frac{1}{{\ln }^{\epsilon /19}n})=\frac{n}{d}(1+o(1))$ for $d$-regular graphs with $d\in [{\ln }^{1+\epsilon }n,n/{\ln }^{\epsilon }n]$, and improving an earlier general upper bound: $s(G)<6\frac{n}{\delta }+6$ of Kalkowski, Karoński and Pfender.

Updated reference