## Abstract

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 c_{1}, c_{2} 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.

Original language | English (US) |
---|---|

Pages (from-to) | 791-826 |

Number of pages | 36 |

Journal | Combinatorica |

Volume | 43 |

Issue number | 4 |

DOIs | |

State | Published - Aug 2023 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Computational Mathematics

## Keywords

- Faudree–Lehel conjecture
- Irregular edge labeling
- Irregularity strength of a graph