In graph theory, a graceful labeling of a graph with edges is a labeling of its vertices with some subset of the integers from 0 to 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 inclusive. Virginia Vassilevska, "Coding and Graceful Labeling of trees." SURF 2001
PostScript
/ref> A graph which admits a graceful labeling is called a graceful graph. The name "graceful labeling" is due to

Solomon W. Golomb Solomon Wolf Golomb (; May 30, 1932 – May 1, 2016) was an American mathematician, engineer, and professor of electrical engineering at the University of Southern California, best known for his works on mathematical games. Most notably, he inve ...

; this type of labeling was originally given the name β-labeling by Alexander Rosa in a 1967 paper on graph labelings.. A major conjecture in graph theory is the graceful tree conjecture or Ringel–Kotzig conjecture, named after

Gerhard Ringel Gerhard Ringel (October 28, 1919 in Kollnbrunn, Austria – June 24, 2008 in Santa Cruz, California) was a German mathematician. He was one of the pioneers in graph theory and contributed significantly to the proof of the Heawood conjecture (now ...

and Anton Kotzig, and sometimes abbreviated GTC. 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. Kotzig once called the effort to prove the conjecture a "disease".. Another weaker version of graceful labelling is near-graceful labeling, in which the vertices can be labeled using some subset of the integers on 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 ). Another conjecture in graph theory is Rosa's Conjecture, named after Alexander Rosa, which says that all triangular cacti are graceful or nearly-graceful.. A graceful graph with edges 0 to is conjectured to have no fewer than

\lceil \sqrt \rfloor

vertices, due to

sparse ruler A sparse ruler is a ruler in which some of the distance marks may be missing. More abstractly, a sparse ruler of length L with m marks is a sequence of integers a_1, a_2, ..., a_m where 0 = a_1 < a_2 < ... < a_m = L. The marks

a_1

results. This conjecture has been verified for all graphs with 213 or fewer edges. Toroidal6

Selected results

*In his original paper, Rosa proved that an

Eulerian graph In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends ...

with number of edges ''m'' ≡ 1 (mod 4) or ''m'' ≡ 2 (mod 4) cannot be graceful. *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 graph In graph theory, a caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path. Caterpillars were first studied in a series of papers by Harary and Schwenk. The name was suggested by Arthur Hobb ...

s are graceful. *All

lobster graph This partial list of graphs contains definitions of graphs and graph families which are known by particular names, but do not have a Wikipedia article of their own. For collected definitions of graph theory terms that do not refer to individual ...

s with a

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...

are graceful.. *All trees with at most 27 vertices are graceful; this result was shown by Aldred and McKay in 1998 using a computer program.. This was extended to trees with at most 29 vertices in the Honours thesis of Michael Horton.. 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.. See als
Graceful Tree Verification Project
/ref> *All wheel graphs, web graphs,

helm graph This partial list of graphs contains definitions of graphs and graph families which are known by particular names, but do not have a Wikipedia article of their own. For collected definitions of graph theory terms that do not refer to individual g ...

gear graph This partial list of graphs contains definitions of graphs and graph families which are known by particular names, but do not have a Wikipedia article of their own. For collected definitions of graph theory terms that do not refer to individual g ...

s, and

rectangular grid A regular grid is a tessellation of ''n''-dimensional Euclidean space by congruent parallelotopes (e.g. bricks). Its opposite is irregular grid. Grids of this type appear on graph paper and may be used in finite element analysis, finite volume ...

s are graceful. *All ''n''-dimensional

hypercube In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1- skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, ...

s are graceful.. *All

simple graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

s with four or fewer vertices are graceful. The only non-graceful simple graphs with five vertices are the 5-

cycle Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in soc ...

(

pentagon In geometry, a pentagon (from the Greek πέντε ''pente'' meaning ''five'' and γωνία ''gonia'' meaning ''angle'') is any five-sided polygon or 5-gon. The sum of the internal angles in a simple pentagon is 540°. A pentagon may be simpl ...

); the complete graph ''K''₅; and the butterfly graph.{{mathworld, title=Graceful graph, urlname=GracefulGraph

References

External links

Numberphile video about graceful tree conjecture

Selected results

See also

References

External links

Further reading