Séminaire Lotharingien de Combinatoire, 78B.86 (2017), 11 pp.
Matthias Beck and Maryam Farahmand
Partially Magic Labelings and the Antimagic Graph Conjecture
Abstract.
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 to a given vertex are distinct. On the
other extreme, an edge labeling is magic if the sums of the
labels on all edges incident to each vertex are the same. In this
paper we approach antimagic labelings by introducing partially
magic labelings, where "magic occurs" just in a subset of V. We
generalize Stanley's theorem about the magic graph labeling counting
function to the associated counting function of partially magic
labelings and prove that it is a quasi-polynomial of period at most
2. This allows us to introduce weak antimagic labelings (for
which repetition is allowed), and we show that every bipartite graph
satisfies a weakened version of the Antimagic Graph Conjecture.
Received: November 14, 2016.
Accepted: February 17, 2017.
Final version: April 1, 2017.
The following versions are available: