Irregularity strength of regular graphs

Jakub Przybyło

The electronic journal of combinatorics, Tome 15 (2008)

Résumé

Let $G$ be a simple graph with no isolated edges and at most one isolated vertex. For a positive integer $w$, a $w$-weighting of $G$ is a map $f:E(G)\rightarrow \{1,2,\ldots,w\}$. An irregularity strength of $G$, $s(G)$, is the smallest $w$ such that there is a $w$-weighting of $G$ for which $\sum_{e:u\in e}f(e)\neq\sum_{e:v\in e}f(e)$ for all pairs of different vertices $u,v\in V(G)$. A conjecture by Faudree and Lehel says that there is a constant $c$ such that $s(G)\le{n\over d}+c$ for each $d$-regular graph $G$, $d\ge 2$. We show that $s(G) < 16{n\over d}+6$. Consequently, we improve the results by Frieze, Gould, Karoński and Pfender (in some cases by a $\log n$ factor) in this area, as well as the recent result by Cuckler and Lazebnik.

Détail

DOI : 10.37236/806

Classification : 05C75
Mots-clés : irregularity strength, graph weighting, regular graph