A generalization of Faudree–Lehel conjecture holds almost surely for random graphs. Issue 2 (7th November 2021) - Przybyło, Jakub
Abstract: The irregularity strength of a simple graph G = ( V, E ), denoted s ( G ) 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 ω : E → { 1, 2, …, k }, assigning every vertex v ∈ V the weighted degree σ ( v ) : = ∑ e ∋ v ω ( e ) . In this setting, s ( G ) 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 s ( G ) > n / d in the case of d ‐regular graphs with order n and d > 1 . An open conjecture of Faudree and Lehel from the 1980s states that s ( G ) ≤ n / d + c 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 G ∈ 𝒢 ( n, p ) for any constant p, that is, that s ( G ) takes one of the three values: ⌈ n / δ ⌉, ⌈ n / δ ⌉ + 1, or ⌈ n / δ ⌉ + 2 . This is implied by the fact that a.a.s. p − 1 < s ( G ) ≤ ⌈ p − 1 ⌉ + 2, and hence n / δ < s ( G ) < n / δ + 3 .