Tutte seminar - Dan McQuillan

Kotzig Arrays and Magic Labelings

Abstract:

A total labeling is a bijective assignment of integers 1,2,3,.. to the vertices and edges of a graph. A vertex-magic total labeling (VMTL) has the added property that for each vertex v, the sum of its label and its incident edge labels is a constant. A VMTL is strong if the smallest labels are assigned to the edges and the largest are assigned to the vertices. It is unknown which 2-regular graphs have a strong VMTL. We discuss recent progress on this problem, using many different applications of Kotzig arrays. A Kotzig array is a jxk matrix, each row being a permutation of {0,1,...,k-1} and each column having constant column sum.