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

Jakub Przybyło, Fan Wei

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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 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.

Original languageEnglish (US)
Pages (from-to)791-826
Number of pages36
JournalCombinatorica
Volume43
Issue number4
DOIs
StatePublished - Aug 2023
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

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

Fingerprint

Dive into the research topics of 'On the Asymptotic Confirmation of the Faudree–Lehel Conjecture for General Graphs'. Together they form a unique fingerprint.

Cite this