2023/07/31 by Johnny Sierra, Sierra, Johnny, Daphne Der‐Fen Liu +3
Computer Science · #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2307.16836
openalex publication_date 2023/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An antimagic labeling of a graph G(V,E) is a bijection f: E → \1,2, …, |E|\ so that ∑e ∈ E(u) f(e) ≠ ∑e ∈ E(v) f(e) holds for all u, v ∈ V(G) with u ≠ 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.