Graceful Graph

A graceful graph is a graph that can be gracefully labeled. Special cases of graceful graphs include the utility graph (Gardner 1983) and Petersen graph. A graph that cannot be gracefully labeled is called an ungraceful (or sometimes disgraceful) graph.

Graceful graphs may be connected or disconnected; for example, the graph disjoint union of the singleton graph and a complete graph is graceful iff (Gallian 2018).

Although an unpublished result of Erdős says that most graphs are not graceful (Graham and Sloane 1980), most graphs that have some sort of regularity of structure are graceful (Gallian 2018).

It is an unsolved and apparently very difficult problem to determine which graphs are graceful. One reason for its difficulty is that a subgraph of a graceful graph need not be graceful (Seoud and Wilson 1993).

In order for a graph to be graceful, it must be without loops or multiple edges. A graph on vertices and edges must also satisfy

in order to be graceful, since otherwise there are not enough integers less than or equal to m to cover all the vertices. Another criterion than can be used to determine a graph is ungraceful is due to Rosa (1967), who proved that an Eulerian graph with edge count congruent to 1 or 2 (mod 4) is ungraceful.

The numbers of graceful graphs on , 2, ... nodes are 1, 1, 2, 7, 22, 126, ... (OEIS A308548), while the corresponding numbers of connected graceful graphs are 1, 1, 2, 6, 18, 106, ... (OEIS A308549). The numbers of ungraceful graphs on , 2, ... nodes are 0, 1, 2, 4, 12, 30, 85, ... (OEIS A308556), with the corresponding numbers of connected ungraceful graphs 0, 0, 0, 0, 3, 6, 34, ... (OEIS A308557), the first few of which are illustrated above.

Parametrized families of graceful graphs include the following:

1. banana trees,

2. book graphs ,

3. caterpillar graphs,

4. complete graphs iff (Golomb 1974),

5. complete bipartite graphs (Golomb 1974),

6. cycle graphs iff ,

7. firecracker graphs,

8. gear graphs,

9. grid graphs ,

10. helm graphs,

11. hypercube graphs ,

12. ladder graphs ,

13. Möbius ladders ,

14. Mongolian tent graphs,

15. pan graphs,

16. path graphs ,

17. Platonic graphs (Gardner 1983, pp. 158 and 163-164),

18. prism graphs ,

19. star graphs ,

20. sunlet graphs ,

21. tadpole graphs,

22. web graphs, and

23. wheel graphs (Frucht 1988).

The -barbell graph is ungraceful for and 5 (E. Weisstein, Aug. 15, 2020) and likely all larger .

Since a tree on vertiecs has edges, all values 0 to appear in any graceful labeling of its vertices. As a result, the edge label can occur only when the edge in question is incident on vertices with labels 0 and , meaning vertex labels 0 and must occur at adjacent vertices in a graceful labeling (Hotron 2003, p. 7). Nikoloski et al. (2002) found an algorithm that uses a triangular tableau to identify and ignore cases of this type (Horton 2003, p. 7). It is conjectured that all trees are graceful (Bondy and Murty 1976), but this has only been verified for trees with graph vertices (Aldred and McKay 1998), a result later extended to 28 (Horton 2003) and 35 vertices. However, the disjoint union of two trees is always ungraceful (Seoud and Wilson 1993).

It has also been conjectured that all unicyclic graphs except the cycle graph with or 2 (mod 4) are graceful (Truszczyński 1984, Gallian 2018).