Approximate results for rainbow labelings

A simple graph \(G=(V,\,E)\) is said to be antimagic if there exists a bijection \(f{\text {:}}\,E\rightarrow 1,\,|E|]\) such that the sum of the values of f on edges incident to a vertex takes different values on distinct vertices. The graph G is distance antimagic if there exists a bijection \(f{\text {:}}\,V\rightarrow 1,\, |V|],\) such that \(\forall x,\,y\in V,\)

$$\begin{aligned} \sum _{x_i\in N(x)}f\left( x_i\right) \ne \sum _{x_j\in N(y)}f\left( x_j\right) . \end{aligned}$$

Using the polynomial method of Alon we prove that there are antimagic injections of any graph G with n vertices and m edges in the interval \(1,\,2n+m-4]\) and, for trees with k inner vertices, in the interval \(1,\,m+k].\) In particular, a tree all of whose inner vertices are adjacent to a leaf is antimagic. This gives a partial positive answer to a conjecture by Hartsfield and Ringel. We also show that there are distance antimagic injections of a graph G with order n and maximum degree \(\Delta \) in the interval \(1,\,n+t(n-t)],\) where \( t=\min \{\Delta ,\,\lfloor n/2\rfloor \},\) and, for trees with k leaves, in the interval \(1,\, 3n-4k].\) In particular, all trees with \(n=2k\) vertices and no pairs of leaves sharing their neighbour are distance antimagic, a partial solution to a conjecture of Arumugam.