2024/03/07 by Margaret M. Bayer, Amanda Burcroff, Bayer, Margaret +5
Computer Science · Engineering · Mathematics · #05C30 (Secondary) #05C78 (Primary) 52B20 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Rings, Modules, and Algebras #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2403.04129
openalex publication_date 2024/03/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A magic labeling of a graph is a labeling of the edges by nonnegative integers such that the label sum over the edges incident to every vertex is the same. This common label sum is known as the index. We count magic labelings by maximum edge label, rather than index, using an Ehrhart-theoretic approach. In contrast to Stanley's 1973 work showing that the function counting magic labelings with bounded index is a quasipolynomial with quasiperiod 2, we show by construction that the minimum quasiperiod of the quasipolynomial counting magic labelings with bounded maximum label can be arbitrarily large, even for planar bipartite graphs. Unfortunately, this rules out a certain Ehrhart-theoretic approach to proving Hartsfield and Ringel's Antimagic Graph Conjecture. However, we show that this quasipolynomial is in fact a polynomial for any bipartite graph with matching preclusion number at most 1, which includes any bipartite graph with a leaf.