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, \ldots, 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 \geq 3\). We also show how these arrays can be used to produce vertex-magic labelings for certain families of graphs.