TOPICS
Search

Graceful Graph


A graceful graph is a graph that can be gracefully labeled. Special cases of graceful graphs include the utility graph K_(2,3) (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 K_1 union K_n of the singleton graph K_1 and a complete graph K_n is graceful iff n<=4 (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 n vertices and m edges must also satisfy

 n<=m+1

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.

UngracefulGraphs

The numbers of graceful graphs on n=1, 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 n=1, 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 B_(2m),

3. caterpillar graphs,

4. complete graphs K_n iff n<=4 (Golomb 1974),

5. complete bipartite graphs K_(m,n) (Golomb 1974),

6. cycle graphs C_n iff n=0 or 3 (mod 4),

7. firecracker graphs,

8. gear graphs,

9. grid graphs P_n square P_m,

10. helm graphs,

11. hypercube graphs Q_n,

12. ladder graphs P_2 square P_n,

13. Möbius ladders M_n,

14. Mongolian tent graphs,

15. pan graphs,

16. path graphs P_n,

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

18. prism graphs K_2 square C_n,

19. star graphs S_n,

20. sunlet graphs C_n circledot K_1,

21. tadpole graphs,

22. web graphs, and

23. wheel graphs W_n (Frucht 1988).

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

Since a tree on n vertiecs has m=n-1 edges, all values 0 to m-1 appear in any graceful labeling of its vertices. As a result, the edge label m-1 can occur only when the edge in question is incident on vertices with labels 0 and m-1, meaning vertex labels 0 and m-1 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 <=27 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 C_n with n=1 or 2 (mod 4) are graceful (Truszczyński 1984, Gallian 2018).


See also

Edge-Graceful Graph, Graceful Labeling, Graceful Permutation, Harmonious Graph, Labeled Graph, Perfect Ruler, Ungraceful Graph

Explore with Wolfram|Alpha

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.Aldred, R. E. L. and McKay, B. "Graceful and Harmonious Labellings of Trees." Bull. Inst. Combin. Appl. 23, 69-72, 1998.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.Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 248, 1976.Brualdi, R. A. and McDougal, K. F. "Semibandwidth of Bipartite Graphs and Matrices." Ars Combin. 30, 275-287, 1990.Brundage, M. "Graceful Graphs." http://www.qbrundage.com/michaelb/pubs/graceful/.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.Eshghi, K. and Azimi, P. "Applications Of Mathematical Programming in Graceful Labeling of Graphs." J. Appl. Math. 2004, no. 1, 1-8, 2004.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.Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Gardner, M. "Mathematical Games: The Graceful Graphs of Solomon Golomb, or How to Number a Graph Parsimoniously." Sci. Amer. 226, No. 3, 108-113, March 1972.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. "How to Number a Graph." In Graph Theory and Computing (Ed. R. C. Read). New York: Academic Press, pp. 23-37, 1972.Golomb, S. W. "The Largest Graceful Subgraph of the Complete Graph." Amer. Math. Monthly 81, 499-501, 1974.Graham, R. L. and Sloane, N. J. A. "On Additive Bases and Harmonious Graphs." SIAM J. Alg. Discrete Methods 1, 382-404, 1980.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.Horton, M. "Graceful Trees: Statistics and Algorithms." Bachelor of Computing with Honours thesis. University of Tasmania, 2003. https://eprints.utas.edu.au/19/1/GracefulTreesStatisticsAndAlgorithms.pdf.Huang, J. H. and Skiena, S. "Gracefully Labelling Prisms." Ars Combin. 38, 225-242, 1994.Jungreis, D. S. and Reid, M. "Labelling Grids." Ars Combin. 34, 167-182, 1992.Knuth, D. E. §7.2.2.3 in The Art of Computer Programming, Vol. 4B: Combinatorial Algorithms, Part 2. New York: Addison-Wesley, 2022.Koh, K. M. and Punnim, N. "On Graceful Graphs: Cycles with 3-Consecutive Chords." Bull. Malaysian Math. Soc. 5, 49-64, 1982.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.Nikoloski, Z.; Deo, N.; and Suraweera, F. "Generation of Graceful Trees." In 33rd Southeastern International Conference on Combinatorics, Graph Theory and Computing. 2002.Punnim, N. and Pabhapote, N. "On Graceful Graphs: Cycles with a P_k-Chord, k>=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.Seoud, M. A. and Wilson, R. J. "Some Disgraceful Graphs." Int. J. Math. Educ. Sci. Tech. 24, 435-441, 1993.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.Sloane, N. J. A. Sequences A308544, A308545, A308548, A308549, A308556, and A308557 in "The On-Line Encyclopedia of Integer Sequences."Snevily, H. S. "New Families of Graphs That Have alpha-Labellings." Preprint.Snevily, H. S. "Remarks on the Graceful Tree Conjecture." Preprint.Truszczyński, M. "Graceful Unicyclic Graphs." Demonstatio Math. 17, 377-387, 1984.Xie, L. T. and Liu, G. Z. "A Survey of the Problem of Graceful Trees." Qufu Shiyuan Xuebao 1, 8-15, 1984.

Referenced on Wolfram|Alpha

Graceful Graph

Cite this as:

Weisstein, Eric W. "Graceful Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GracefulGraph.html

Subject classifications