2022/03/28 by Angel Chavez, Parker Le, Chavez, Angel +6 · 1 citation
Computer Science · #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2203.14842
Let G be a graph with m edges and let f be a bijection from E(G) to \1,2, …, m\. For any vertex v, denote by ϕf(v) the sum of f(e) over all edges e incident to v. If ϕf(v) ≠ ϕf(u) holds for any two distinct vertices u and v, then f is called an \it antimagic labeling of G. We call G \it antimagic if such a labeling exists. Hartsfield and Ringel in 1991 conjectured that all connected graphs except P2 are antimagic. Denote the disjoint union of graphs G and H by G ∪ H, and the disjoint union of t copies of G by tG. For an antimagic graph G (connected or disconnected), we define the parameter τ(G) to be the maximum integer such that G ∪ tP3 is antimagic for all t ≤ τ(G). Chang, Chen, Li, and Pan showed that for all antimagic graphs G, τ(G) is finite [Graphs and Combinatorics 37 (2021), 1065--1182]. Further, Shang, Lin, Liaw [Util. Math. 97 (2015), 373--385] and Li [Master Thesis, National Chung Hsing University, Taiwan, 2019] found the exact value of τ(G) for special families of graphs: star forests and balanced double stars respectively. They did this by finding explicit antimagic labelings of G∪ tP3 and proving a tight upper bound on τ(G) for these special families. In the present paper, we generalize their results by proving an upper bound on τ(G) for all graphs. For star forests and balanced double stars, this general bound is equivalent to the bounds given in \citestar forest and \citedouble star and tight. In addition, we prove that the general bound is also tight for every other graph we have studied, including an infinite family of jellyfish graphs, cycles Cn where 3 ≤ n ≤ 9, and the double triangle 2C3.