by Michael Brundage
Occasionally mathematics provides problems which simultaneously challenge professional mathematicians and yet put original results within reach of motivated high school or undergraduate students. Gracefully labelling graphs is one such problem. To date, most research has focused on specific classes of graphs, and few general results are known.
Consider an undirected graph with N edges. Label each vertex of the graph with one of the numbers from 0 to N inclusive. Not every number must be used, but no number may be used more than once. Now label each edge with the absolute difference of the labels of its endpoints. The labeling is graceful if the edges are labelled 1 through N inclusive (no number repeated). A graceful graph is a graph that has at least one graceful labeling.
Figure 1-1 below depicts a graceful labeling of the complete graph on four vertices, K4. The graph has six edges, so the integers 0 through 6, inclusive, are available for vertex labels. If we use the numbers 0, 1, 4, and 6, and compute the edge labels, then every number from 1 to 6 appears as an edge label. Therefore, K4 is graceful.
Figure 1-1: A graceful graph with six edges.
Graceful graphs are attractive to mathematicians because they are so easy to describe, yet lead to many difficult (and as yet unanswered) questions and computational problems. Perhaps the most outstanding one is: Are all trees graceful? But there are many other questions surrounding graceful graphs.
Graceful graphs are related to many other mathematical topics including Golomb rulers, permutations, and other graph labeling problems. They have some practical applications such as radio astronomy, but for the most part graceful graphs are just mathematical curiosities.
I became interested in graceful graphs as part of an undergraduate research seminar course I took at Caltech in 1993-1994. Almost immediately I obtained some computational results, but I didn't know what to do with them -- they were too trivial to merit formal publication. The web had just come into existence, and publishing online seemed worthwhile. So I wrote this up and put it on the Caltech undergraduate web server.
These web pages moved with me to the University of Washington from 1994-1996, and then moved back to Caltech from 1996-1999, and well, you get the picture – lots of broken links all over. In 2004, I finally got around to updating the information and putting it online again, resulting in the collection you see here.
The exposition here is purposely aimed at an introductory level; anyone with a basic understanding of mathematics should be able to understand it. Although I have taken care to ensure the quality and factual correctness of this site, I am only human. Please email michaelb AT qbrundage.com with your corrections and suggestions.
Copyright © Michael Brundage, 1993-2004