Graceful Graph

A Labeled Graph which can be ``gracefully numbered'' is called a graceful graph. Label the nodes with distinct Nonnegative Integers. Then label the Edges with the absolute differences between node values. If the Edge numbers then run from 1 to $e$, the graph is gracefully numbered. In order for a graph to be graceful, it must be without loops or multiple Edges.

Golomb showed that the number of Edges connecting the Even-numbered and Odd-numbered sets of nodes is $\left\lfloor{(e+1)/2}\right\rfloor$, where $e$ is the number of Edges. In addition, if the nodes of a graph are all of Even Order, then the graph is graceful only if $\left\lfloor{(e+1)/2}\right\rfloor$ is Even. The only ungraceful simple graphs with $\leq 5$ nodes are shown below.

There are exactly $e!$ graceful graphs with $e$ Edges (Sheppard 1976), where $e!/2$ of these correspond to different labelings of the same graph. Golomb (1974) showed that all complete bipartite graphs are graceful. Caterpillar Graphs; Complete Graphs $K_2$, $K_3$, $K_4=W_4=T$ (and only these; Golomb 1974); Cyclic Graphs $C_n$ when $n\equiv 0{\rm\ or\ }3\ \left({{\rm mod\ } {4}}\right)$, when the number of consecutive chords $k=2$, 3, or $n-3$ (Koh and Punnim 1982), or when they contain a $P_k$ chord (Delorme et al. 1980, Koh and Yap 1985, Punnim and Pabhapote 1987); Gear Graphs; Path Graphs; the Petersen Graph; Polyhedral Graphs $T=K_4=W_4$, $C$, $O$, $D$, and $I$ (Gardner 1983); Star Graphs; the Thomsen Graph (Gardner 1983); and Wheel Graphs (Frucht 1988) are all graceful.

Some graceful graphs have only one numbering, but others have more than one. It is conjectured that all trees are graceful (Bondy and Murty 1976), but this has only been proved for trees with $\leq 16$ Vertices. It has also been conjectured that all unicyclic graphs are graceful.

See also Harmonious Graph, Labeled Graph

References

Abraham, J. and Kotzig, A. ``All 2-Regular Graphs Consisting of 4-Cycles are Graceful.'' Disc. Math. 135, 1-24, 1994.

Abraham, J. and Kotzig, A. ``Extensions of Graceful Valuations of 2-Regular Graphs Consisting of 4-Gons.'' Ars Combin. 32, 257-262, 1991.

Bloom, G. S. and Golomb, S. W. ``Applications of Numbered Unidirected Graphs.'' Proc. IEEE 65, 562-570, 1977.

Bolian, L. and Xiankun, Z. ``On Harmonious Labellings of Graphs.'' Ars Combin. 36, 315-326, 1993.

Brualdi, R. A. and McDougal, K. F. ``Semibandwidth of Bipartite Graphs and Matrices.'' Ars Combin. 30, 275-287, 1990.

Cahit, I. ``Are All Complete Binary Trees Graceful?'' Amer. Math. Monthly 83, 35-37, 1976.

Delorme, C.; Maheo, M.; Thuillier, H.; Koh, K. M.; and Teo, H. K. ``Cycles with a Chord are Graceful.'' J. Graph Theory 4, 409-415, 1980.

Frucht, R. W. and Gallian, J. A. ``Labelling Prisms.'' Ars Combin. 26, 69-82, 1988.

Gallian, J. A. ``A Survey: Recent Results, Conjectures, and Open Problems in Labelling Graphs.'' J. Graph Th. 13, 491-504, 1989.

Gallian, J. A. ``Open Problems in Grid Labeling.'' Amer. Math. Monthly 97, 133-135, 1990.

Gallian, J. A. ``A Guide to the Graph Labelling Zoo.'' Disc. Appl. Math. 49, 213-229, 1994.

Gallian, J. A.; Prout, J.; and Winters, S. ``Graceful and Harmonious Labellings of Prism Related Graphs.'' Ars Combin. 34, 213-222, 1992.

Gardner, M. ``Golomb's Graceful Graphs.'' Ch. 15 in Wheels, Life, and Other Mathematical Amusements. New York: W. H. Freeman, pp. 152-165, 1983.

Golomb, S. W. ``The Largest Graceful Subgraph of the Complete Graph.'' Amer. Math. Monthly 81, 499-501, 1974.

Guy, R. ``Monthly Research Problems, 1969-75.'' Amer. Math. Monthly 82, 995-1004, 1975.

Guy, R. ``Monthly Research Problems, 1969-1979.'' Amer. Math. Monthly 86, 847-852, 1979.

Guy, R. K. ``The Corresponding Modular Covering Problem. Harmonious Labelling of Graphs.'' §C13 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 127-128, 1994.

Huang, J. H. and Skiena, S. ``Gracefully Labelling Prisms.'' Ars Combin. 38, 225-242, 1994.

Koh, K. M. and Punnim, N. ``On Graceful Graphs: Cycles with $3$-Consecutive Chords.'' Bull. Malaysian Math. Soc. 5, 49-64, 1982.

Jungreis, D. S. and Reid, M. ``Labelling Grids.'' Ars Combin. 34, 167-182, 1992.

Koh, K. M. and Yap, K. Y. ``Graceful Numberings of Cycles with a $P_3$-Chord.'' Bull. Inst. Math. Acad. Sinica 13, 41-48, 1985.

Moulton, D. ``Graceful Labellings of Triangular Snakes.'' Ars Combin. 28, 3-13, 1989.

Murty, U. S. R. and Bondy, J. A. Graph Theory with Applications. New York: North Holland, p. 248, 1976.

Punnim, N. and Pabhapote, N. ``On Graceful Graphs: Cycles with a $P_k$-Chord, $k\geq 4$.'' Ars Combin. A 23, 225-228, 1987.

Rosa, A. ``On Certain Valuations of the Vertices of a Graph.'' In Theory of Graphs, International Symposium, Rome, July 1966. New York: Gordon and Breach, pp. 349-355, 1967.

Sheppard, D. A. ``The Factorial Representation of Balanced Labelled Graphs.'' Discr. Math. 15, 379-388, 1976.

Sierksma, G. and Hoogeveen, H. ``Seven Criteria for Integer Sequences Being Graphic.'' J. Graph Th. 15, 223-231, 1991.

Slater, P. J. ``Note on $k$-Graceful, Locally Finite Graphs.'' J. Combin. Th. Ser. B 35, 319-322, 1983.

Snevily, H. S. ``New Families of Graphs That Have $\alpha$-Labellings.'' Preprint.

Snevily, H. S. ``Remarks on the Graceful Tree Conjecture.'' Preprint.

Xie, L. T. and Liu, G. Z. ``A Survey of the Problem of Graceful Trees.'' Qufu Shiyuan Xuebao 1, 8-15, 1984.