View source for Graceful labeling

{{short description|Type of graph vertex labeling}}
[[Image:Graceful labeling.svg|thumb|A graceful labeling. [[Vertex (graph theory)|Vertex]] labels are in black, edge labels in red.]]
{{unsolved|mathematics|Do all trees admit a graceful labeling?}}

In [[graph theory]], a '''graceful labeling''' of a [[Graph (discrete mathematics)|graph]] with {{mvar|m}} edges is a [[graph labeling|labeling]] of its [[Vertex (graph theory)|vertices]] with some subset of the [[integer]]s from 0 to {{mvar|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 {{mvar|m}} inclusive.<ref name="Vas2001">[[Virginia Vassilevska Williams|Virginia Vassilevska]],  "Coding and Graceful Labeling of trees." SURF 2001. [https://www.cs.cmu.edu/~virgi/final1.ps PostScript]</ref>  A graph which admits a graceful labeling is called a '''graceful graph'''.

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.<ref name="Ros1967">{{citation
 | last = Rosa | first = A.
 | contribution = On certain valuations of the vertices of a graph
 | location = New York
 | mr = 0223271
 | pages = 349–355
 | publisher = Gordon and Breach
 | title = Theory of Graphs (Internat. Sympos., Rome, 1966)
 | year = 1967}}.</ref>

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).<ref>{{citation
 | last1 = Wang | first1 = Tao-Ming
 | last2 = Yang | first2 = Cheng-Chang
 | last3 = Hsu | first3 = Lih-Hsing
 | last4 = Cheng | first4 = Eddie
 | doi = 10.2298/AADM141009017W
 | issue = 1
 | journal = Applicable Analysis and Discrete Mathematics
 | mr = 3362693
 | pages = 1–12
 | title = Infinitely many equivalent versions of the graceful tree conjecture
 | volume = 9
 | year = 2015| doi-access = free
 }}</ref> 
It hypothesizes that all [[tree (graph)|tree]]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.<ref>{{Cite arXiv|title=A proof of Ringel's Conjecture|eprint=2001.02665|language=en|last1=Montgomery|first1=Richard|last2=Pokrovskiy|first2=Alexey|last3=Sudakov|first3=Benny|year=2020|class=math.CO}}</ref><ref>{{citation|last1=Huang|first1=C.|title=Further results on tree labellings|journal=Utilitas Mathematica|volume=21|pages=31–48|year=1982|mr=668845|last2=Kotzig|first2=A.|last3=Rosa|first3=A.|author2-link=Anton Kotzig}}.</ref><ref>{{Cite web|url=https://www.quantamagazine.org/mathematicians-prove-ringels-graph-theory-conjecture-20200219/|title=Rainbow Proof Shows Graphs Have Uniform Parts|last=Hartnett|first=Kevin|website=Quanta Magazine|date=19 February 2020 |language=en|access-date=2020-02-29}}</ref> 
<!--[Incorrect?  Graceful labeling refers to all graphs, not just trees.]  The Ringel–Kotzig conjecture is also known as the "graceful labeling conjecture".--> 
Kotzig once called the effort to prove the conjecture a "disease".<ref name="Hua1982">{{citation
 | last1 = Huang | first1 = C.
 | last2 = Kotzig | first2 = A. | author2-link = Anton Kotzig
 | last3 = Rosa | first3 = A.
 | journal = Utilitas Mathematica
 | mr = 668845
 | pages = 31–48
 | title = Further results on tree labellings
 | volume = 21
 | year = 1982}}.</ref>

Another weaker version of graceful labelling is '''near-graceful labeling''', in which the vertices can be labeled using some subset of the [[integer]]s on {{math|[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 {{math|[1, ''m'' + 1]}}).

Another conjecture in graph theory is '''Rosa's conjecture''', named after Alexander Rosa, which says that all [[Cactus graph#Triangular cactus|triangular cacti]] are graceful or nearly-graceful.<ref name="Rosa1988">{{citation|last=Rosa|first=A.|title=Cyclic Steiner Triple Systems and Labelings of Triangular Cacti|journal=Scientia|volume=1|pages=87–95|year=1988}}.</ref>

A graceful graph with edges 0 to {{mvar|m}} is conjectured to have no fewer than <math> \left\lceil \sqrt{3 m+\tfrac{9}{4}} \right\rfloor </math> 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 2{{mvar|m}}-valence graceful graph has <math>3 m^2</math> edges, with the case for 6-valence shown below.
[[File:Toroidal6.png|thumb|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.<ref name="Ros1967"/>
*Also in his original paper, Rosa proved that the cycle ''C<sub>n</sub>'' is graceful if and only if ''n'' ≡ 0 (mod 4) or ''n'' ≡ 3 (mod 4).
*All [[path graph]]s and [[caterpillar graph]]s are graceful.<ref name="Ros1967" />
*All [[lobster graph]]s with a [[perfect matching]] are graceful.<ref name="Morgan">{{citation
 | last = Morgan | first = David
 | journal = Bulletin of the Institute of Combinatorics and Its Applications
 | pages = 82–85
 | title = All lobsters with perfect matchings are graceful
 | volume = 53
 | year = 2008| hdl = 10402/era.26923
 }}.</ref>
*All trees with at most 27 vertices are graceful; this result was shown by Aldred and [[Brendan McKay (mathematician)|McKay]] in 1998 using a computer program.<ref name="Gal2015">{{citation
 | last = Gallian | first = Joseph A. | author-link = Joseph Gallian
 | journal = Electronic Journal of Combinatorics
 | mr = 1668059
 | page = Dynamic Survey 6, 43 pp. (389 pp. in 18th ed.) (electronic)
 | title = A dynamic survey of graph labeling
 | url = http://www.combinatorics.org/ojs/index.php/eljc/article/viewFile/DS6/pdf
 | volume = 5
 | year = 1998}}.</ref><ref>{{citation
 | last1 = Aldred | first1 = R. E. L.
 | last2 = McKay | first2 = Brendan D. | author2-link = Brendan McKay (mathematician)
 | journal = Bulletin of the Institute of Combinatorics and Its Applications
 | mr = 1621760
 | pages = 69–72
 | title = Graceful and harmonious labellings of trees
 | volume = 23
 | year = 1998}}.</ref> This was extended to trees with at most 29 vertices in the Honours thesis of Michael Horton.<ref name="Horton2003">{{citation
 | last = Horton | first = Michael P. | author-link = Michael P. Horton
 | title = Graceful Trees: Statistics and Algorithms
 | url = http://eprints.utas.edu.au/19/
 | year = 2003| publisher = University of Tasmania | doi = 10.25959/23212346.v1 }}.</ref> 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.<ref>{{citation
 | last = Fang | first = Wenjie
 | arxiv = 1003.3045| title = A Computational Approach to the Graceful Tree Conjecture
 | year = 2010| bibcode = 2010arXiv1003.3045F}}.  See also [https://web.archive.org/web/20120729224449/http://www.eleves.ens.fr/home/wfang/gtv/index_en.html Graceful Tree Verification Project]</ref>
*All [[wheel graph]]s, web graphs, [[helm graph]]s, [[gear graph]]s, and [[grid graph#Square grid graph|rectangular grid]]s are graceful.<ref name="Gal2015"/>
*All ''n''-dimensional [[hypercube]]s are graceful.<ref name="Kot1981">{{citation
 | last = Kotzig | first = Anton | author-link = Anton Kotzig
 | doi = 10.1016/0095-8956(81)90031-9
 | issue = 3
 | journal = Journal of Combinatorial Theory, Series B
 | mr = 638285
 | pages = 292–296
 | title = Decompositions of complete graphs into isomorphic cubes
 | volume = 31
 | year = 1981| doi-access = free
 }}.</ref>
*All [[simple graph|simple]] [[connected graph]]s with four or fewer vertices are graceful. The only non-graceful simple connected graphs with five vertices are the 5-[[cycle graph|cycle]] ([[pentagon]]); the [[complete graph#Examples|complete graph ''K''<sub>5</sub>]]; and the [[butterfly graph]].<ref name="Mat2007">{{mathworld|title=Graceful graph|urlname=GracefulGraph}}</ref>

==See also==
*[[Edge-graceful labeling]]
*[[List of conjectures]]

==References==
<references/>

== External links ==

* [https://www.youtube.com/watch?v=v5KWzOOhZrw Numberphile video about graceful tree conjecture]
* [https://mathworld.wolfram.com/GracefulLabeling.html Graceful labeling in mathworld]

==Further reading==
* (K. Eshghi) [http://sharif.edu/~eshghi/Graceful%20Graphs-Final%20Edition-89-12-15.pdf  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 (graph theorist)|Ping Zhang]]), A Kaleidoscopic View of Graph Colorings, SpringerBriefs in Mathematics, 2016 – Springer

[[Category:Graph theory objects]]
[[Category:Conjectures]]