2021/09/27 by Przybyło, Jakub, Wei, Fan · 1 citation
#05C07 #05C35 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2109.13095
Given a simple graph G, the \it irregularity strength of G, denoted s(G), is the least positive integer k such that there is a weight assignment on edges f: E(G) → \1,2,…, k\ for which each vertex weight fV(v):= ∑_u: \u,v\∈ E(G) f(\u,v\) is unique amongst all v∈ V(G). In 1987, Faudree and Lehel conjectured that there is a constant c such that s(G) ≤ n/d + c for all d-regular graphs G on n vertices with d>1, whereas it is trivial that s(G) ≥ n/d. In this short note we prove that the Faudree-Lehel Conjecture holds when d ≥ n0.8+ε for any fixed ε>0, with a small additive constant c=28 for d large enough. Furthermore, we confirm the conjecture asymptotically by proving that for any fixed β∈(0,1/4) there is a constant C such that for all d-regular graphs G, s(G) ≤ (n)/(d)(1+(C)/(dβ))+28, extending and improving a recent result of Przybyło that s(G) ≤ (n)/(d)(1+ \frac1lnε/19n) whenever d∈ [ln1+ε n, n/lnεn] and d is large enough.