Edge irregular total labellings for graphs of linear size
Confirming a conjecture by Ivanˇco and Jendrol for a large class of graphs we prove that for every graph G = (V,E) of order n, size m and maximum degree with m > 111000 there is a function f : V [ E ! 1, 2, ..., m+2 3 such that f(u) + f(uv) + f(v) 6= f(u0) + f(u0v0) + f(v0) for every uv, u0v0 2 E with uv 6= u0v0. Furthermore, we prove the existence of such a function with values up to m 2 for every graph G = (V,E) of order n and size m 3 whose edges are not all incident to a single vertex.
Use and reproduction:
All rights reserved