Distant sum distinguishing index of graphs

Abstract

Consider a positive integer $r$ and a graph $G=(V,E)$ with maximum degree $\Delta$ and without isolated edges. The least $k$ so that 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$ is denoted by ${\chi }_{\Sigma ,r}^{\prime }(G)$. For $r=1$ it has been proved that ${\chi }_{\Sigma ,1}^{\prime }(G)=(1+o(1))\Delta$. For any $r\ge 2$ in turn an infinite family of graphs is known with ${\chi }_{\Sigma ,r}^{\prime }(G)=\Omega ({\Delta }^{r-1})$. We prove that on the other hand, ${\chi }_{\Sigma ,r}^{\prime }(G)=O({\Delta }^{r-1})$ for $r\ge 2$. In particular we show that ${\chi }_{\Sigma ,r}^{\prime }(G)\le 6{\Delta }^{r-1}$ if $r\ge 4$.

10 pages

References in corpus (4)

• On the neighbour sum distinguishing index of planar graphs
• A note on asymptotically optimal neighbour sum distinguishing colourings
• Distant irregularity strength of graphs with bounded minimum degree
• Distant set distinguishing edge colourings of graphs