 | ||
A magic graph is a graph whose edges are labelled by positive integers, so that the sum over the edges incident with any vertex is the same, independent of the choice of vertex; or it is a graph that has such a labelling. If the integers are the first q positive integers, where q is the number of edges, the graph and the labelling are called supermagic.
A graph is vertex-magic if its vertices can be labelled so that the sum on any edge is the same. It is total magic if its edges and vertices can be labelled so that the vertex label plus the sum of labels on edges incident with that vertex is a constant.
There are a great many variations on the concept of magic labelling of a graph. There is much variation in terminology as well. The definitions here are perhaps the most common.
Comprehensive references for magic labellings and magic graphs are Gallian (1998), Wallis (2001), and Marr and Wallis (2013).
Magic squares
A semimagic square is an n × n square with the numbers 1 to n2 in its cells, in which the sum of each row and column is the same. A semimagic square is equivalent to a magic labelling of the complete bipartite graph Kn,n. The two vertex sets of Kn,n correspond to the rows and the columns of the square, respectively, and the label on an edge risj is the value in row i, column j of the semimagic square. (A semimagic square is often called a magic square in mathematics, but it does not have all the properties of a magic square.)