Antimagic Labelings of Forests

Abstract

An antimagic labeling of a graph $G(V,E)$ is a bijection $f:E\to \{1,2,\dots ,|E|\}$ so that ${\sum }_{e\in E(u)}f(e)\ne {\sum }_{e\in E(v)}f(e)$ holds for all $u,v\in V(G)$ with $u\ne v$, where $E(v)$ is the set of edges incident to $v$. We call $G$ antimagic if it admits an antimagic labeling. A forest is a graph without cycles; equivalently, every component of a forest is a tree. It was proved by Kaplan, Lev, and Roditty [2009], and by Liang, Wong, and Zhu [2014] that every tree with at most one vertex of degree-2 is antimagic. A major tool used in the proof is the zero-sum partition introduced by Kaplan, Lev, and Roditty [2009]. In this article, we provide an algorithmic representation for the zero-sum partition method and apply this method to show that every forest with at most one vertex of degree-2 is also antimagic.

arXiv comment12 pages, 11 figures