Distant sum distinguishing index of graphs with bounded minimum degree

Abstract

For any graph $G=(V,E)$ with maximum degree $\Delta$ and without isolated edges, and a positive integer $r$, by ${\chi }_{\Sigma ,r}^{\prime }(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\to \{1,2,\dots ,k\}$ exists such that ${\sum }_{e\ni u}c(e)\ne {\sum }_{e\ni v}c(e)$ for every pair of distinct vertices $u,v$ at distance at most $r$ in $G$. It was conjectured that ${\chi }_{\Sigma ,r}^{\prime }(G)\le (1+o(1)){\Delta }^{r-1}$ for every $r\ge 3$. Thus far it has been in particular proved that ${\chi }_{\Sigma ,r}^{\prime }(G)\le 6{\Delta }^{r-1}$ if $r\ge 4$. Combining probabilistic and constructive approach, we show that this can be improved to ${\chi }_{\Sigma ,r}^{\prime }(G)\le (4+o(1)){\Delta }^{r-1}$ if the minimum degree of $G$ equals at least ${\ln }^8\Delta$.

arXiv comment12 pages