One does not often use the term magic when referring to a mathematical idea. Proof, theorem, unequivocal truth all come up much more often. The one case that many people will be acquainted with are Magic Squares. Magic Squares are square arrays of integers such that all of the rows, columns, and diagonals sum to the same integer. I on the other hand am much more interested in a different, albeit similar, type of Magic; the magic of certain types of edge labelings of graphs.
The graphs I refer to are not the lines and parabolas of middle school algebra, nor are they the stock price plots and histograms from newspapers. These graphs are a much more abstract concept derived from the work of the great Swiss mathematician Leonhard Euler, of vertices that are connected together by edges. This has turned out to be an incredibly powerful tool in mathematics that has led to major results which include, but in no way are limited to, that four is the maximum number of colors needed to fill in a map so no two bordering countries are the same color and a more effective method for the prediction of just when a disease, such as the swine flu, is going to reach epidemic status. An edge labeling of one of these graphs is exactly what it sounds like, placing labels on the edges of these graphs. The specific type of labeling here requires all the labels to be integers that are not 0. After a graph has an edge labeling it is then possible to create a vertex labeling by summing together all of the labels of the edges that connect to a vertex.
Graph with Edge labeling
Graph with Vertex Labeling
If this vertex labeling is constant, the same for all vertices, then it is said that edge labeling is magic.
Graph with a magic edge labeling
Before I go any deeper into a discussion of this please determine a magic labeling for the following two graphs.
Graph 1
For a mathematician just finding a couple of these magic-labelings would be fun but ultimately not very interesting, so let us start to restrict ourselves. Let us begin by only labeling the edges of our graphs with positive integers that are less than some integer n. Once there are labels on the edges the next step is to find the vertex labels and here in is the second restriction, addition modulo n. Modular addition, written as a+b mod n, is equal to the remainder of a+b when it is divided by n. Take for example 4+3 mod 2. This is equal to 1, since 1 is the remainder when 7 is divided by two. In a similar way 4+2 mod 3 equals 0, can you see why? If we try to label with these restrictions we could just maybe, begin to see patterns.
In fact, mathematicians refer to all of the integers n such that there is magic labeling under this restriction as the integer-magic spectrum of the graph. Some graphs have integer-magic spectrums that contain all of the positive integers, such as Graph 1. Others have more limited integer-magic spectrums, Graph 2 is a good example as its integer-magic spectrum is all of the even numbers greater than 2. Then you have examples, like the graph below, which allows no magic labeling, or in other words is just not magic.
In order to have even more fun some mathematicians, one who even looks very remarkably like myself, have asked the following question: Which members of the integer-magic spectrum of a graph allow a vertex labeling of 0. If there is such a zero magic-labeling then it is said that n is in the null-set of the integer-magic spectrum of the graph. I happen to know the null sets for the graphs pictured above, can you find them?
3 Comments