dimacs logo

General Information

Name: Tim Reynolds (timbreynolds@gmail.com)
Home University: Massachusetts Institute of Technology
Mentor: Tao-Ming Wang, Tung-Hai University, Taiwan
Project: Antimagic Labellings in Graphs
Office: CoRE 634

Project Description

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.


Progress Log

Week 1 (June 1-June 5)
Read Cranston's paper
Proved Hartsfield and Ringel's conjecture for the case of two n-cycles with each vertex of one connected to a single vertex of the other

Week 2 (June 6-June 12)
Prepared for presentation
Worked on antimagic labellings of Generalized Petersen Graphs
Attended seminar by Daniel Kral on matchings in graphs

Week 3 (June 13-June 19)
Began considering Zk-magic labellings and edge-antimagic labellings

Week 4 (June 20-June 26)
Worked on calculating the deficiency of complete graphs and complete bipartite graphs
Found an upper bound for the deficiency of Kmn, and proved it is the exact value of the deficiency of K_{4,n}

Week 5 (June 27-July 3)
Continued to work on deficiency of complete bipartite graphs and complete graphs
Proved result on Zk-magic spectra of 3- and 4-regular graphs


References

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