Towards generalizing MacDougall’s Conjecture on Vertex-magic total labelings

Around the turn of the century, labeling of graphs started to become popular due to an increase in applications of graph theory to complex networks. One variation of graph labeling involves using numbers 1,2,3,… on both the vertices (or nodes) and the links between vertices (edges). At each vertex, we add its label to the labels of all of its incident edges, to get the vertex’s weight. The labeling is called vertex-magic, if all vertices have the same weight. Most graphs don’t have a vertex-magic labeling. MacDougall’s conjecture (approximately) states that as long as every vertex has the same number of incident edges, then it does have one. Most experts believe the conjecture is true. We examined a natural generalization of MacDougall’s Conjecture and demonstrated it to be false. Specifically, we ask if the list of degrees of the vertices would determine whether or not the graph has a vertex-magic labeling. It does not. We provide infinitely many degree sequences, and for each sequence, a graph with a vertex-magic labeling and another graph without a vertex-magic labeling.

Our paper, appearing in the journal Discrete Mathematics (2020), is the culmination of at least a decade of total work, including substantial contributions from two former Norwich University students, Keith Gibson (2014) and Artmiz Golkaramnay (2017).