2013/06/07 by Matthias Beck, Beck, Matthias, Michael Jackanich +1
Computer Science · Mathematics · #05C22 #05C31 #05C78 #52B20 #52C35 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1306.1763
openalex publication_date 2013/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Antimagic Graph Conjecture asserts that every connected graph G = (V, E) except K2 admits an edge labeling such that each label 1, 2, ..., |E| is used exactly once and the sums of the labels on all edges incident with a given node are distinct. We study an associated counting function (replacing the upper bound on the possible labels by a variable) and prove that a variant of this counting function, when we do not require the labels to be distinct, is a polynomial if G is bipartite. As a consequence, we show that every connected bipartite graph G = (V, E) except K2 admits a weakly antimagic labeling, that is, each edge label is among 1, 2, ..., |E| (repetition allowed) and the sums of the labels on all edges incident with a given node are distinct. We also present a natural extension of these results to directed and bidirected graphs; this extension gives rise to a (bi-)directed version of the Antimagic Graph Conjecture, which might be of independent interest.