pith. sign in

arxiv: 1703.03712 · v1 · pith:GLL5SSJInew · submitted 2017-03-10 · 🧮 math.CO

Distant sum distinguishing index of graphs

classification 🧮 math.CO
keywords deltasigmagraphsbeencolouringconsiderdegreedenoted
0
0 comments X
read the original 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,\ldots,k\}$ exists such that $\sum_{e\ni u}c(e)\neq \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}(G)$. For $r=1$ it has been proved that $\chi'_{\Sigma,1}(G)=(1+o(1))\Delta$. For any $r\geq 2$ in turn an infinite family of graphs is known with $\chi'_{\Sigma,r}(G)=\Omega(\Delta^{r-1})$. We prove that on the other hand, $\chi'_{\Sigma,r}(G)=O(\Delta^{r-1})$ for $r\geq 2$. In particular we show that $\chi'_{\Sigma,r}(G)\leq 6\Delta^{r-1}$ if $r\geq 4$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.