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 , … , 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 ) ≤ n d + C for each d ‐regular graph G with n vertices and d ≥ 2 (while a straightforward counting argument yields s ( G ) ≥ n + d − 1 d ). The best known results towards this imply that s ( G ) ≤ 6⌈ n d ⌉ for every d ‐regular graph G with n vertices and d ≥ 2 , while s ( G ) ≤ ( 4 + o ( 1 ) ) n d + 4 if d ≥ 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 ∈ [ ln 8 n , n ln 3 n] , s ( G ) ≤ n d ( 1 + 8 ln n) , and thereby we show that s ( G ) = n d ( 1 + o ( 1 ) ) then. We moreover prove the latter to hold already when d ∈ [ ln 1 + ε n , n ln ε n] , where ε is an arbitrary positive constant.