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

05C75 Structural characterization of families of graphs
Full Text: EMIS EuDML