Magic squares and antimagic graphs

P. Mark Kayll
Department of Mathematical Sciences
University of Montana
Missoula MT 59812-0864, USA
mark.kayll@umontana.edu

Abstract

An antimagic labeling of a graph with m edges is a bijection from its edge set to such that the vertex sums are distinct, a vertex sum being the sum of the -values on the edges incident with the vertex. An antimagic graph is one that admits such a labeling. It was conjectured in [N. Hartsfield and G. Ringel, Supermagic and antimagic graphs, J. Recreational Math. 21 (1989), 107–115] that every connected graph other than K₂ is antimagic. We verify this conjecture constructively for a class of graphs derived from the complete graphs K_n = (V,E) using a variant of magic squares. In support of our main result, we establish that K_n, with , possesses a property stronger than being antimagic: for every function , there exists a bijectionsuch that the sums , for , are all different. This ‘robust’ property of K_n proves useful in establishing that graphs of the form K_n − F, for certain , are antimagic.

Keywords: antimagic, latin square, magic square, RC-magic, transversal system

AMS Subject Classification: Primary 05C78 Secondary 05C50, 05B15