Edge irregular total labellings for graphs of linear size

As an edge variant of the well-known irregularity strength of a graph G=(V,E) we investigate edge irregular total labellings, i.e. functions f:V∪E→{1,2,…,k} such that f(u)+f(uv)+f(v)≠f(u^′)+f(u^′v^′)+f(v^′) for every pair of different edges uv,u^′v^′∈E. The smallest possible k is the total edge irregularity strength of G. Confirming a conjecture by Ivan?o and Jendrol’ for a large class of graphs we prove that the natural lower bound is tight for every graph of order n, size m and maximum degree Δ with m>111000Δ. This also implies that the probability that a random graph from G(n,p(n)) satisfies the Ivan?o-Jendrol’ Conjecture tends to 1 as n→∞ for all functions p∈0,1]^N. Furthermore, we prove that is an upper bound for every graph G of order n and size m≥3 whose edges are not all incident to a single vertex.