2006/03/04 by Yongxi Cheng, Cheng, Yongxi
Computer Science · Mathematics · #05C78 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.math/0603106
openalex publication_date 2006/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An 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 antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every connected graph, but K2, is antimagic. In 2004, N. Alon et al showed that this conjecture is true for n-vertex graphs with minimum degree Ω(log n). They also proved that complete partite graphs (other than K2) and n-vertex graphs with maximum degree at least n-2 are antimagic. Recently, Wang showed that the toroidal grids (the Cartesian products of two or more cycles) are antimagic. Two open problems left in Wang's paper are about the antimagicness of lattice grid graphs and prism graphs, which are the Cartesian products of two paths, and of a cycle and a path, respectively. In this article, we prove that these two classes of graphs are antimagic, by constructing such antimagic labelings.