Antimagic labelings of regular bipartite graphs: An application of the Marriage Theorem

Abstract

A labeling of a graph is a bijection from $E(G)$ to the set $\{1,2,...,|E(G)|\}$. A labeling is \textit{antimagic} if for any distinct vertices $u$ and $v$, the sum of the labels on edges incident to $u$ is different from the sum of the labels on edges incident to $v$. We say a graph is antimagic if it has an antimagic labeling. In 1990, Ringel conjectured that every connected graph other than $K_2$ is antimagic. In this paper, we show that every regular bipartite graph (with degree at least 2) is antimagic. Our technique relies heavily on the Marriage Theorem.

arXiv comment9 pages

References in corpus (1)

• Dense graphs are antimagic