Distant irregularity strength of graphs with bounded minimum degree

Consider a graph G=(V,E) without isolated edges and with maximum degree Δ. Given a colouring c:E→{1,2,…,k}, the weighted degree of a vertex v∈V is the sum of its incident colours, i.e., ∑e∋vc(e). For any integer r≥2, the least k admitting the existence of such c attributing distinct weighted degrees to any two different vertices at distance at most r in G is called the r-distant irregularity strength of G and denoted by sr(G). This graph invariant provides a natural link between the well known 1-2-3 Conjecture and irregularity strength of graphs. In this paper we apply the probabilistic method in order to prove an upper bound sr(G)≤(4+o(1))Δr−1 for graphs with minimum degree δ≥ln8Δ, improving thus far best upper bound sr(G)≤6Δr−1.