The University of Montana
Department of Mathematical Sciences

Technical report #16/2007

Magic squares and antimagic graphs

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

Jennifer McNulty
Department of Mathematical Sciences
University of Montana
Missoula MT 59812-0864, USA
jenny.mcnulty@umontana.edu

James Mihalisin
Department of Mathematical Sciences
University of Montana
Missoula MT 59812-0864, USA
mihalisi@mso.umt.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), 107115] that every connected graph other than K2 is antimagic. We verify this conjecture constructively for a class of graphs derived from the complete graphs Kn = (V,E) using a variant of magic squares. In support of our main result, we establish that Kn, 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 Kn proves useful in establishing that graphs of the form KnF, for certain , are antimagic.

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

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

Download Technical Report: Pdf (144 KB)