In
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, 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 discre ...
with edges is a
labeling of its
vertices with some subset of the
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s 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 ...
and Anton Kotzig, and sometimes abbreviated GTC.
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, including only woody plants with secondary growth, plants that are ...
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 integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s 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 vertices, due to sparse ruler results. This conjecture has been verified for all graphs with 213 or fewer edges.
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.
*Also in his original paper, Rosa proved that the cycle ''Cn'' 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 terminal ...
s and caterpillar graphs 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 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 / 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. Not ...
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
A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another from any system. Distributed computing is a field of computer sci ...
project led by Wenjie Fang.[. See als]
Graceful Tree Verification Project
/ref>
*All wheel graphs, web graphs, helm graphs, 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 ...
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 connected graphs 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 soc ...
(pentagon
In geometry, a pentagon (from the Greek language, 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 polygon, simple pentagon is ...
); the complete graph ''K''5; and the butterfly graph.[{{mathworld, title=Graceful graph, urlname=GracefulGraph]
See also
* Edge-graceful labeling
* List of conjectures
References
External links
Numberphile video about graceful tree conjecture
Further reading
* (K. Eshghi
Introduction to Graceful Graphs
Sharif University of Technology, 2002.
* (U. N. Deshmukh and Vasanti N. Bhat-Nayak), New families of graceful banana trees – Proceedings Mathematical Sciences, 1996 – Springer
* (M. Haviar, M. Ivaska), Vertex Labellings of Simple Graphs, Research and Exposition in Mathematics, Volume 34, 2015.
* ( Ping Zhang), A Kaleidoscopic View of Graph Colorings, SpringerBriefs in Mathematics, 2016 – Springer
Graph theory objects
Conjectures