Sparse Semi-Magic Squares and Vertex-magic Labelings

Abstract

We introduce a generalisation of the traditional magic square, which proves useful in the construction of magic labelings of graphs. An order $n$ sparse semi-magic square is an $n\times n$ array containing the entries $1,2,\dots ,m$ (for some $m<n^2$) once each with the remainder of its entries $0$, and its rows and columns have a constant sum $k$. We discover some of the basic properties of such arrays and provide constructions for squares of all orders $n\ge 3$. We also show how these arrays can be used to produce vertex-magic labelings for certain families of graphs.