Graceful labeling

In graph theory, a graceful labeling of a graph with m edges is a labeling of its vertices with some subset of the integers from 0 to m inclusive, such that no two vertices share a label, and each edge is uniquely identified by the absolute difference between its endpoints, such that this magnitude lies between 1 and m inclusive.^[1] A graph which admits a graceful labeling is called a graceful graph.

A graceful labeling. Vertex labels are in black, edge labels in red.

Unsolved problem in mathematics

Do all trees admit a graceful labeling?

More unsolved problems in mathematics

The name "graceful labeling" is due to Solomon W. Golomb; this type of labeling was originally given the name β-labeling by Alexander Rosa in a 1967 paper on graph labelings.^[2]

A major open problem in graph theory is the graceful tree conjecture or Ringel–Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, and sometimes abbreviated GTC (not to be confused with Kotzig's conjecture on regularly path connected graphs).^[3] It hypothesizes that all trees are graceful. It is still an open conjecture, although a related but weaker conjecture known as "Ringel's conjecture" was partially proven in 2020.^[4][5][6] Kotzig once called the effort to prove the conjecture a "disease".^[7]

Another weaker version of graceful labelling is near-graceful labeling, in which the vertices can be labeled using some subset of the integers on [0, m + 1] such that no two vertices share a label, and each edge is uniquely identified by the absolute difference between its endpoints (this magnitude lies on [1, m + 1]).

Another conjecture in graph theory is Rosa's conjecture, named after Alexander Rosa, which says that all triangular cacti are graceful or nearly-graceful.^[8]

A graceful graph with edges 0 to m is conjectured to have no fewer than ${\displaystyle \left\lceil {\sqrt {3m+{\tfrac {9}{4}}}}\right\rfloor }$ vertices, due to sparse ruler results. This conjecture has been verified for all graphs with 213 or fewer edges. A related conjecture is that the smallest 2m-valence graceful graph has ${\displaystyle 3m^{2}}$ edges, with the case for 6-valence shown below.

A graceful graph with 27 edges and 9 vertices

Selected results

• In his original paper, Rosa proved that an Eulerian graph with number of edges m ≡ 1 (mod 4) or m ≡ 2 (mod 4) cannot be graceful.^[2]
• Also in his original paper, Rosa proved that the cycle C_n is graceful if and only if n ≡ 0 (mod 4) or n ≡ 3 (mod 4).
• All path graphs and caterpillar graphs are graceful.^[2]
• All lobster graphs with a perfect matching are graceful.^[9]
• All trees with at most 27 vertices are graceful; this result was shown by Aldred and McKay in 1998 using a computer program.^[10][11] This was extended to trees with at most 29 vertices in the Honours thesis of Michael Horton.^[12] Another extension of this result up to trees with 35 vertices was claimed in 2010 by the Graceful Tree Verification Project, a distributed computing project led by Wenjie Fang.^[13]
• All wheel graphs, web graphs, helm graphs, gear graphs, and rectangular grids are graceful.^[10]
• All n-dimensional hypercubes are graceful.^[14]
• All simple connected graphs with four or fewer vertices are graceful. The only non-graceful simple connected graphs with five vertices are the 5-cycle (pentagon); the complete graph K₅; and the butterfly graph.^[15]

See also

• Edge-graceful labeling
• List of conjectures