Approximate results for rainbow labelings

详细信息    查看全文

• 作者：Anna Lladó ; Mirka Miller
• 关键词：Graph labeling ; Polynomial method
• 刊名：Periodica Mathematica Hungarica
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：74
• 期：1
• 页码：11-21
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics, general;
• 出版者：Springer Netherlands
• ISSN：1588-2829
• 卷排序：74

文摘

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.KeywordsGraph labelingPolynomial methodMirka Miller passed away in January 2016. This paper was written during successive meetings with Mirka in Jakarta, Bandung, Barcelona and Vientiane. After a long friendship full of mathematical discussions, this is the only mathematical paper that the two of us wrote together, not knowing that it would also be the last one. It is with a mixing of happiness and sorrow that I can eventually see it in print.