A new class of antimagic Cartesian product graphs

作者：Cheng Yongxi^*

来源：Discrete Mathematics, 2008, 308(24): 6441-6448.

DOI：10.1016/j.disc.2007.12.032

• Antimagic
• Magic
• Labeling
• Regular graph
• Cartesian product

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 I 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 [N. Hartsfield. G. Ringel, Pearls in Graph Theory, Academic Press, INC., Boston, 1990, pp. 108-109, Revised version, 1994] conjectured that every simple connected graph, except K(2), is antimagic. In this article, we prove that a new class of Cartesian product graphs are antimagic. In particular, by combining this result and the antimagicness result on toroidal grids (Cartesian products of two cycles) in [Tao-Ming Wang, Toroidal grids are anti-magic, in: Proc. 11th Annual International Computing and Combinatorics Conferences COCOON'2005, in: LNCS, vol. 3595, Springer, 2005, pp. 671-679], all Cartesian products of two or more regular graphs of positive degree can be proved to be antimagic.

• 出版日期2008-12-28
• 单位清华大学