graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a graceful labeling of a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

with edges is a

labeling Labelling or using a label is describing someone or something in a word or short phrase. For example, the label "criminal" may be used to describe someone who has broken a law. Labelling theory is a theory in sociology which ascribes labelling ...

of its vertices with some subset of the

integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

s from 0 to inclusive, such that no two vertices share a label, and each edge is uniquely identified by the

absolute difference The absolute difference of two real numbers x and y is given by , x-y, , the absolute value of their difference. It describes the distance on the real line between the points corresponding to x and y, and is a special case of the Lp distance fo ...

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. He most notably inven ...

; this type of labeling was originally given the name β-labeling by Alexander Rosa in a 1967 paper on graph labelings.. A major open problem 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 Anton Kotzig (22 October 1919 – 20 April 1991) was a Slovak–Canadian mathematician, expert in statistics, combinatorics and graph theory. A number of his mathematical contributions are named after him. These include the Ringel–Kotzig con ...

, and sometimes abbreviated GTC (not to be confused with

Kotzig's conjecture Kotzig's conjecture is an unproven assertion in graph theory which states that finite graphs with certain properties do not exist. A graph is a P_k-graph if each pair of distinct vertices is connected by ''exactly one'' path of length k. Kotzi ...

on regularly path connected graphs). It hypothesizes that all

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...

s 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

s on such that no two vertices share a label, and each edge is uniquely identified by the

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

\left\lceil \sqrt \right\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. A related conjecture is that the smallest 2-valence graceful graph has

3 m^2

edges, with the case for 6-valence shown below. 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 graph In the mathematical field of graph theory, a path graph (or linear graph) is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...

s and caterpillar graphs are graceful. *All lobster graphs 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 with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exact ...

are graceful.. *All trees with at most 27 vertices are graceful; this result was shown by Aldred and

McKay McKay, MacKay or Mackay is a Scottish and Irish surname. The last phoneme in the name is traditionally pronounced to rhyme with 'eye', but in some parts of the world this has come to rhyme with 'hey'. In Scotland, it corresponds to Clan Mackay. ...

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 Distributed computing is a field of computer science that studies distributed systems, defined as computer systems whose inter-communicating components are located on different networked computers. The components of a distributed system commu ...

project led by Wenjie Fang.. See als
Graceful Tree Verification Project
/ref> *All

wheel graph In graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with vertices can also be defined as the 1-skeleton of an pyramid. Some authors write to denote a wheel graph ...

s, web graphs,

helm graph This partial list of Graph (discrete mathematics), graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as ''vertex'' and ''path'', see Glossary ...

gear graph This partial list of Graph (discrete mathematics), graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as ''vertex'' and ''path'', see Glossary ...

s, and rectangular grids are graceful. *All ''n''-dimensional

hypercube In geometry, a hypercube is an ''n''-dimensional analogue of a square ( ) and a cube ( ); the special case for is known as a ''tesseract''. It is a closed, compact, convex figure whose 1- skeleton consists of groups of opposite parallel l ...

s are graceful.. *All

simple Simple or SIMPLE may refer to: *Simplicity, the state or quality of being simple Arts and entertainment * ''Simple'' (album), by Andy Yorke, 2008, and its title track * "Simple" (Florida Georgia Line song), 2018 * "Simple", a song by John ...

connected graph In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgrap ...

s with four or fewer vertices are graceful. The only non-graceful simple connected 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 ...

(

pentagon In geometry, a pentagon () is any five-sided polygon or 5-gon. The sum of the internal angles in a simple polygon, simple pentagon is 540°. A pentagon may be simple or list of self-intersecting polygons, self-intersecting. A self-intersecting ...

); the complete graph ''K''₅; and the

butterfly graph In the mathematics, mathematical field of graph theory, the butterfly graph (also called the bowtie graph and the hourglass graph) is a planar graph, planar, undirected graph with 5 Vertex (graph theory), vertices and 6 edges. It can be construct ...

.{{mathworld, title=Graceful graph, urlname=GracefulGraph

References

External links

Numberphile video about graceful tree conjecture

Selected results

See also

References

External links

Further reading