Distant sum distinguishing index of graphs with bounded minimum degree

Abstract

For any graph G = (V, E) with maximum degree Δ and without isolated edges, and a positive integer r, by χ′_Σ, r(G) we denote the r-distant sum distinguishing index of G. This is the least integer k for which a proper edge colouring c: E → {1, 2, …, k} exists such that ∑_e∋uc(e) ≠ ∑_e∋vc(e) for every pair of distinct vertices u, v at distance at most r in G. It was conjectured that χ′_Σ, r(G) ≤ (1 + o(1))Δ^r − 1 for every r ≥ 3. Thus far it has been in particular proved that χ′_Σ, r(G) ≤ 6Δ^r − 1 if r ≥ 4. Combining probabilistic and constructive approach, we show that this can be improved to χ′_Σ, r(G) ≤ (4 + o(1))Δ^r − 1 if the minimum degree of G equals at least ln⁸ Δ.