Bipartite graphs are weak antimagic

Abstract

The \emph{Antimagic Graph Conjecture} asserts that every connected graph $G=(V,E)$ except $K_2$ 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 $K_2$ admits a \emph{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.

This paper has been withdrawn due to a flaw in the proof of the main result

References in corpus (2)

• Lectures on 0/1-polytopes
• Regular graphs of odd degree are antimagic