The irregularity strength of dense graphs -- on asymptotically optimal solutions of problems of Faudree, Jacobson, Kinch and Lehel

The irregularity strength of a graph G, $s(G)$, is the least k such that there exists a \1,2,…,k\-weighting of the edges of G attributing distinct weighted degrees to all vertices, or equivalently the least k enabling obtaining a multigraph with nonrecurring degrees by blowing each edge e of G to at most k copies of e. In 1991 Faudree, Jacobson, Kinch and Lehel asked for the optimal lower bound for the minimum degree of a graph G of order n which implies that s(G)≤ 3. More generally, they also posed a similar question regarding the upper bound s(G)≤ K for any given constant K. We provide asymptotically tight solutions of these problems by proving that such optimal lower bound is of order 1/K-1n for every fixed integer K≥ 3.