# zbMATH — the first resource for mathematics

Irregularity strength of regular graphs. (English) Zbl 1163.05329
Summary: 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,\dots,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 R.J. Faudree and J. Lehel [Combinatorics, Proc. 7th Hung. Colloq., Eger/Hung. 1987, Colloq. Math. Soc. János Bolyai 52, 247-256 (1988; Zbl 0697.05048)] says that there is a constant $$c$$ such that $$s(G)\leq\frac{n}{d}+c$$ for each $$d$$-regular graph $$G, d\geq 2$$. We show that $$s(G)< 16\frac{n}{d}+6$$. Consequently, we improve the results by A. Frieze, R.J. Gould, M. Karoński, and F. Pfender [J. Graph Theory 41, No. 2, 120–137 (2002; Zbl 1016.05045)] (in some cases by a $$\log n$$ factor) in this area, as well as the recent result by B. Cuckler and F. Lazebnik [J. Graph Theory 58, No. 4, 299–313 (2008; Zbl 1188.05112)].

##### MSC:
 05C75 Structural characterization of families of graphs
##### Keywords:
irregularity strength; graph weighting; regular graph
Full Text: