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.

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 conjecture in graph theory is the graceful tree conjecture or Ringel–Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, and sometimes abbreviated GTC.[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 graceful graph with 27 edges and 9 vertices