Antimagic Labeling of Forests

Authors

  • Johnny Sierra California State University, Los Angeles
  • Daphne Der-Fen Liu California State University, Los Angeles
  • Jessica Toy California State University, Los Angeles

DOI:

https://doi.org/10.46787/pump.v6i0.3752

Keywords:

antimagic labeling; antimagic graphs; trees; rooted trees; forests

Abstract

An antimagic labeling of a graph G(V,E) is a bijection f mapping from E to the set {1,2,…, |E|}, so that for any two different vertices u and v, the sum of f(e) over all edges e incident to u, and the sum of f(e) over all edges e incident to v, are distinct.  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 in 2009, and by Liang, Wong, and Zhu in 2014 that every tree with at most one vertex of degree two is antimagic. A major tool used in the proof is the zero-sum partition introduced by Kaplan, Lev, and Roditty in 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 two is also antimagic.

Downloads

Published

2023-08-17

How to Cite

Sierra, J., Liu, D. D.-F., & Toy, J. (2023). Antimagic Labeling of Forests. The PUMP Journal of Undergraduate Research, 6, 268–279. https://doi.org/10.46787/pump.v6i0.3752