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: