A generalization of Faudree–Lehel conjecture holds almost surely for random graphs. Issue 2 (7th November 2021)

• Record Type: Journal Article
• Authors: Przybyło, Jakub
• Is Part Of: Random structures & algorithms. Volume 61:Issue 2(2022)
• Page Start: 383
• Page End: 396
• Publication Date: 2021-11-07
• Subjects: Faudree–Lehel conjecture -- irregular edge weighting -- irregularity strength of a graph -- Jacobson's conjecture -- random graph; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21058
• Languages: English
• ISSNs: 1042-9832

Abstract

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 .