On the Asymptotic Confirmation of the Faudree–Lehel Conjecture for General Graphs

Given a simple graph G, the irregularity strength of G, denoted by s(G), is the least positive integer k such that there is a weight assignment on edges f: E(G) → { 1 , 2 , ⋯ , k} attributing distinct weighted degrees: f~ (v) : = ∑ u:{u,v}∈E(G)f({ u, v}) to all vertices v∈ V(G) . It is straightforward that s(G) ≥ n/ d for every d-regular graph G on n vertices with d> 1 . In 1987, Faudree and Lehel conjectured in turn that there is an absolute constant c such that s(G) ≤ n/ d+ c for all such graphs. Even though the conjecture has remained open in almost all relevant cases, it is more generally believed that there exists a universal constant c such that s(G) ≤ n/ δ+ c for every graph G on n vertices with minimum degree δ≥ 1 which does not contain an isolated edge; In this paper we confirm that the generalized Faudree–Lehel Conjecture holds for graphs with δ≥ nβ where β is any fixed constant larger than 0.8; Furthermore, we confirm that the conjecture holds in general asymptotically. That is, we prove that for any ε∈ (0 , 0.25) there exist absolute constants c1, c2 such that for all graphs G on n vertices with minimum degree δ≥ 1 and without isolated edges, s(G)≤nδ(1+c1δε)+c2 ; We thereby extend in various aspects and strengthen a recent result of Przybyło, who showed that s(G)≤nd(1+1lnε/19n)=nd(1+o(1)) for d-regular graphs with d∈ [ln 1+εn, n/ ln εn] . We also improve the earlier general upper bound: s(G)<6nδ+6 of Kalkowski, Karoński and Pfender.

Duke Scholars

Author Fan Wei Mathematics