 |
Barbara Smith and Karen Petrie
School of Computing and Engineering, University of Huddersfield
A labelling f of the nodes of a graph with q edges is graceful if f assigns each node a unique label from {0,1,..., q} and when each edge xy is labelled with | f(x) - f(y)|, the edge labels are all different. (Hence, the edge labels are a permutation of 1, 2, ..., q.)
The figure below shows a graceful labelling of the clique K4.
|
[Gallian, 2002] gives a survey of graceful graphs, i.e. graphs with a graceful labelling, and lists the graphs whose status is known.
The material on these pages is based on a recent paper [Petrie and Smith, 2003], available online.