The antimagicness of the Cartesian product of graphs

An antimagic labeling of a graph with M edges and N vertices is a bijection from the set of edges to the set {1,2,3,…,M} such that all the N vertex-sums are pairwise distinct, where the vertex-sum of a vertex v is the sum of labels of all edges incident with v. A graph is called antimagic if it has an antimagic labeling. The antimagicness of the Cartesian product of graphs in several special cases has been studied [Tao-Ming Wang, Toroidal grids are anti-magic, in: Proc. 11th Annual International Computing and Combinatorics Conference, COOCOON’2005, in: LNCS, vol. 3595, Springer, 2005, pp. 671–679, Yongxi Cheng, A new class of antimagic cartesian product graphs, Discrete Mathematics 308 (24) (2008) 6441–6448]. In this paper, we develop new construction methods that are applied to more general cases. We prove that the Cartesian product of paths is antimagic, if one of them has at least three edges. This (almost) answers the open problems in [Yongxi Cheng, Lattice grids and prisms are antimagic, Theoretical Computer Science 374 (2007) 66–73]. We also prove that the Cartesian product of an antimagic regular graph and a connected graph is antimagic, which extends the results of the latter of the two references, where several special cases are studied.