A generalization of Faudree–Lehel conjecture holds almost surely for random graphs
Jakub Przybyło · Random Structures and Algorithms · 2021
Abstract The irregularity strength of a simple graph , denoted is a certain measure of the level of irregularity of a graph. It indicates how hard it is to make an irregular multigraph of G via multiplication of its selected edges. It is however more commonly set forth through k‐weightings, that is, mappings , assigning every vertex the weighted degree . In this setting, is precisely defined as the least k admitting a k‐weighting of G which attributes pairwise distinct weighted degrees to all vertices of G. It is known that in the case of d‐regular graphs with order n and . An open conjecture of Faudree and Lehel from the 1980s states that in turn for some finite constant c independent of d. It is believed that the natural strengthening of this conjecture toward all graphs where d is substituted by the minimum degree should also hold. We confirm this supposition in the case of random graphs. Namely, we show that asymptotically almost surely the generalization of Faudree‐Lehel Conjecture holds for a random graph for any constant p, that is, that takes one of the three values: , , or . This is implied by the fact that a.a.s. , and hence .