Graceful Graphs

Created: Mar 1, 1993; last updated: May 22, 2014

Introduction

In 1993, I took a Caltech undergraduate seminar course taught by (then postdoc) Hunter Snevily. Dr. Snevily encouraged us 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 $(u, v)$ is labelled with the absolute difference $\lvert u - v\rvert$ of its vertex endpoints' labels, and as a result every edge label between $1$ and $\lvert E \rvert$ appears exactly once.

A graceful labeling of the complete graph K4

Many unsolved questions about graceful graphs are simple to state but apparently difficult to prove. Chief among these are:

Question (Ringel & Kotzig, 1982):

Are all trees are graceful?

Question (Truszczynski, 1984):

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

For an extensive list of unsolved problems and progress on graceful and other graph labelings, see 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