Distant set distinguishing edge colourings of graphs

We consider the following extension of the concept of adjacent strong edge colourings of graphs without isolated edges. Two distinct vertices which are at distant at most $r$ in a graph are called $r$-adjacent. The least number of colours in a proper edge colouring of a graph $G$ such that the sets of colours met by any $r$-adjacent vertices in $G$ are distinct is called the $r$-adjacent strong chromatic index of $G$ and denoted by ${\chi }_{a,r}^{\mathrm{\prime }}(G)$. It has been conjectured that ${\chi }_{a,1}^{\mathrm{\prime }}(G)\le \mathrm{\Delta }+2$ if $G$ is connected of maximum degree $\mathrm{\Delta }$ and non-isomorphic to $C_5$, while Hatami proved that there is a constant $C$, $C\le 300$, such that ${\chi }_{a,1}^{\mathrm{\prime }}(G)\le \mathrm{\Delta }+C$ if $\mathrm{\Delta }>{10}^{20}$ [J. Combin. Theory Ser. B 95 (2005) 246–256]. We conjecture that a similar statement should hold for any $r$, i.e., that for each positive integer $r$ there exist constants ${\delta }_0$ and $C$ such that $\chi’{a,r}(G) \leq \Delta+C$foreverygraphwithoutanisolatededgeandwithminimumdegree$\delta \geq \delta_0$,andarguethatalowerboundon$\delta$ is unavoidable in such a case (for $r>2$). Using the probabilistic method we prove such upper bound to hold for graphs with $\delta \ge ϵ\mathrm{\Delta }$, for every $r$ and any fixed $\epsilon \in (0,1]$, i.e., in particular for regular graphs. We also support the conjecture by proving an upper bound $\chi’{a,r}(G) \leq (1+o(1))\Delta$forgraphswith$\delta\geq r+2$.