In a graph with n edges, a labelling is an assignment of the numbers 1 through n to the edges. A magic labelling is one in which the sum of the edges incident to each vertex is the same, while an antimagic labelling is one in which the sums of the edges incident to any two distinct vertices are different. A graph with an antimagic labelling is called antimagic. In 1990, Hartsfield and Ringel conjecture that every connected simple graph except for K2 is antimagic. Alon et al proved that all graphs with sufficiently many edges (that is, some constant times the logarithm of the number of vertices) are antimagic, and Cranston proved that all regular bipartite graphs (except K2) are antimagic. In this project we work towards Hartsfield and Ringel's conjecture, specifically for regular graphs.
In addition to antimagic labellings, I have considered other types of graph labellings. One type is a Zk-magic labelling, in which each edge of a graph is labelled with an element of the group Zk other than 0. My mentor proved in a paper that regular graphs with perfect matchings could be labelled such that, for any element of Zk, the vertices of the graph could be labelled with nonzero elements of Zk to give each vertex that sum. The converse of that theorem is still open: do regular graphs which can attain any vertex sum in Zk for all k necessarily have perfect matchings? If not, for what classes of graphs is this true?
Another class of labellings is edge-antimagic labellings. This is exactly analogous to vertex-antimagic labellings described above: the vertices of the graph must be labelled in such a way such that, for any two edges, the sum of the labels of the two vertices incident to the first edge is different from that of the second edge. Simple combinatorial reasoning shows that an edge-antimagic graph with p vertices can have at most 2p-3 edges. The deficiency of a graph is defined to be the number of lone vertices one must add to make the graph edge-antimagic. Some questions I hope to answer are what conditions are necessary for a graph with 2p-3 edges to admit an edge-antimagic labelling, and what the deficiencies of certain graphs such as Kmn and Kn are.
My first presentation from June 11, 2010 is available here.
My second presentation from July 16, 2010 is available here.
Week 1 (June 1-June 5)
Cranston, D. "Regular Bipartite graphs are antimagic." Journal of Graph Theory Volume 60, Issue 3, March 2009
Gallian, J. "A Dynamic Survey of Graph Labelling." The Electronic Journal of Combinatorics Volume 16, #DS6, January 2009
Last update: 7/6/2010