Graceful Graphs

by Created: 01 Mar 1993 Updated: 22 May 2014

Introduction

In 1993, in an undergraduate Caltech seminar course taught by (then postdoc) Hunter Snevily that I took, the students were encouraged to hunt around and find something interesting to research. After some hours digging through math journals in the library, I stumbled across the topic of graceful graphs.

A graceful graph is a graph whose vertices are labeled with distinct values between 0 and \(\lvert E \rvert\) (the number of edges), each edge is labelled with the absolute difference of its vertex endpoints, and as a result every edge label between 1 and \(\lvert E \rvert\) appears exactly once.

project/graceful/K4.png

Graceful graphs have many unsolved questions that are simple to state but apparently difficult to prove. Chief among these are:

Are all trees are graceful?
Are all unicyclic graphs (except \(C_n,\ n \equiv 1,2 \pmod{4}\)) graceful?

An extensive list of unsolved problems and progress on graceful and other graph labelings can be found in Joseph Gallian’s A Dynamic Survey of Graph Labelling

Graceful graphs lend themselves naturally to computational approaches. I’ve written several programs to explore this space. Often, from a few labelled instances one can find and prove a generic pattern.

Project Pages