Short proof of the asymptotic confirmation of the Faudree-Lehel conjecture

Jakub Przybyło ; Fan Wei¹

¹Princeton University

The electronic journal of combinatorics, Tome 30 (2023) no. 4

Résumé

Given a simple graph $G$, the 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) \to \{1,2,\dots, k\}$ for which each vertex weight $f^V(v):= \sum_{u: \{u,v\}\in E(G)} f(\{u,v\})$ is unique amongst all $v\in V(G)$. In 1987, Faudree and Lehel conjectured that there is a constant $c$ such that $s(G) \leq n/d + c$ for all $d$-regular graphs $G$ on $n$ vertices with $d>1$, whereas it is trivial that $s(G) \geq n/d$. In this short note we prove that the Faudree-Lehel Conjecture holds when $d \geq n^{0.8+\epsilon}$ for any fixed $\epsilon >0$, with a small additive constant $c=28$ for $n$ large enough. Furthermore, we confirm the conjecture asymptotically by proving that for any fixed $\beta\in(0,1/4)$ there is a constant $C$ such that for all $d$-regular graphs $G$, $s(G) \leq \frac{n}{d}(1+\frac{C}{d^{\beta}})+28$, extending and improving a recent result of Przybyło that $s(G) \leq \frac{n}{d}(1+ \frac{1}{\ln^{\epsilon/19}n})$ whenever $d\in [\ln^{1+\epsilon} n, n/\ln^{\epsilon}n]$ and $n$ is large enough.

Détail

DOI : 10.37236/11413

Classification : 05C22, 05C15, 05C78
Mots-clés : edge-weighting function, bounds for regular graphs