Distant total irregularity strength of graphs via random vertex ordering

Let c:V∪E→{1,2,…,k} be a (not necessarily proper) total colouring of a graph G=(V,E) with maximum degree Δ. Two vertices u,v∈V are sum distinguished if they differ with respect to sums of their incident colours, i.e. c(u)+∑e∋uc(e)≠c(v)+∑e∋vc(e). The least integer k admitting such colouring c under which every u,v∈V at distance 1≤d(u,v)≤r in G are sum distinguished is denoted by tsr(G). Such graph invariants link the concept of the total vertex irregularity strength of graphs with so-called 1-2-Conjecture, whose concern is the case of r=1. Within this paper we combine probabilistic approach with purely combinatorial one in order to prove that tsr(G)≤(2+o(1))Δr−1 for every integer r≥2 and each graph G, thus improving the previously best result: tsr(G)≤3Δr−1.