Asymptotic confirmation of the Faudree-Lehel Conjecture on irregularity strength for all but extreme degrees

Abstract

The irregularity strength of a graph $G$, $s(G)$, is the least $k$ admitting a $\{1,2,\dots ,k\}$-weighting of the edges of $G$ assuring distinct weighted degrees of all vertices, or equivalently the least possible maximal edge multiplicity in an irregular multigraph obtained of $G$ via multiplying some of its edges. The most well-known open problem concerning this graph invariant is the conjecture posed in 1987 by Faudree and Lehel that there exists a constant $C$ such that $s(G)\le \frac{n}{d}+C$ for each $d$-regular graph $G$ with $n$ vertices and $d\ge 2$ (while a straightforward counting argument yields $s(G)\ge \frac{n+d-1}{d}$). The best known results towards this imply that $s(G)\le 6\lceil \frac{n}{d}\rceil$ for every $d$-regular graph $G$ with $n$ vertices and $d\ge 2$, while $s(G)\le (4+o(1))\frac{n}{d}+4$ if $d\ge n^{0.5}\ln n$. We show that the conjecture of Faudree and Lehel holds asymptotically in the cases when $d$ is neither very small nor very close to $n$. We in particular prove that for large enough $n$ and $d\in [{\ln }^{8}n,\frac{n}{{\ln }^{3}n}]$, $s(G)\le \frac{n}{d}(1+\frac{8}{\ln n})$, and thereby we show that $s(G)=\frac{n}{d}(1+o(1))$ then. We moreover prove the latter to hold already when $d\in [{\ln }^{1+\epsilon }n,\frac{n}{{\ln }^{\epsilon }n}]$ where $\epsilon$ is an arbitrary positive constant.

arXiv comment14 pages