053: Graceful Graphs

[Gallian] surveys graceful graphs, i.e. graphs with a graceful labelling, and lists the graphs whose status is known.

In regards to Constraint Programming Petrie and Smith [PetrieSmith] in 2003 have shown that $K_4 \times P_2$, $K_4 \times P_3$, $K_4 \times P_4$, $K_4 \times P_5$, are graceful. They also proved that $K_3 \times P_3$ and $K_6 \times P_2$ are not graceful. In 2010 Smith and Puget [SmithPuget] extended this work to show that $K_7 \times P_2$, $K_8 \times P_2$, $K_9 \times P_2$ and $K_{10} \times P_2$ are not graceful.