Distant total sum distinguishing index of graphs

Abstract

Let $c:V\cup E\to \{1,2,\dots ,k\}$ be a proper total colouring of a graph $G=(V,E)$ with maximum degree $\Delta$. We say vertices $u,v\in V$ are sum distinguished if $c(u)+{\sum }_{e\ni u}c(e)\ne c(v)+{\sum }_{e\ni v}c(e)$. By $\chi {"}_{\Sigma ,r}(G)$ we denote the least integer $k$ admitting such a colouring $c$ for which every $u,v\in V$, $u\ne v$, at distance at most $r$ from each other are sum distinguished in $G$. For every positive integer $r$ an infinite family of examples is known with $\chi {"}_{\Sigma ,r}(G)=\Omega ({\Delta }^{r-1})$. In this paper we prove that $\chi {"}_{\Sigma ,r}(G)\le (2+o(1)){\Delta }^{r-1}$ for every integer $r\ge 3$ and each graph $G$, while $\chi {"}_{\Sigma ,2}(G)\le (18+o(1))\Delta$.

10 pages. arXiv admin note: text overlap with arXiv:1703.00376

References in corpus (2)

• A note on asymptotically optimal neighbour sum distinguishing colourings
• Distant total irregularity strength of graphs via random vertex ordering