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