Cartesian Products of Regular Graphs are Antimagic

Abstract

An \emph{antimagic labeling} of a finite undirected simple graph with $m$ edges and $n$ vertices is a bijection from the set of edges to the integers $1,...,m$ such that all $n$ vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with the same vertex. A graph is called \emph{antimagic} if it has an antimagic labeling. In 1990, Hartsfield and Ringel \cite{HaRi} conjectured that every simple connected graph, but $K_2$, is antimagic. In this article, we prove that a new class of Cartesian product graphs are antimagic. In addition, by combining this result and the antimagicness result on toroidal grids (Cartesian products of two cycles) in \cite{Wan}, all Cartesian products of two or more regular graphs can be proved to be antimagic.

10 pages, 2 figures

References in corpus (1)

• Dense graphs are antimagic