TOPICS
Search

Ungraceful Graph


UngracefulGraphs

An ungraceful graph is a simple graph that does not possess a graceful labeling, i.e., a graph that is not a graceful graph (Gardner 1972). Such graphs have also been termed "disgraceful graphs" (Seoud and Wilson 1993).

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. As can be seen, there are no connected ungraceful graphs on fewer than five vertives and exactly three connected ungraceful graphs on five vertices, namely the butterfly graph (Horton 2003), cycle graph C_5, and complete graph K_5.


See also

Graceful Graph, Graceful Labeling

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

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.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.Seoud, M. A. and Wilson, R. J. "Some Disgraceful Graphs." Int. J. Math. Educ. Sci. Tech. 24, 435-441, 1993.

Cite this as:

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