Graceful labeling

{{short description|Type of graph vertex labeling}}

Image:Graceful labeling.svg 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 with {{mvar|m}} edges is a labeling of its vertices with some subset of the integers 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.Virginia Vassilevska, "Coding and Graceful Labeling of trees." SURF 2001. [https://www.cs.cmu.edu/~virgi/final1.ps PostScript] 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.{{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}}.

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).{{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

}}

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.{{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}}{{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}}.{{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}}

Kotzig once called the effort to prove the conjecture a "disease".{{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}}.

Another weaker version of graceful labelling is near-graceful labeling, in which the vertices can be labeled using some subset of the integers 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 triangular cacti are graceful or nearly-graceful.{{citation|last=Rosa|first=A.|title=Cyclic Steiner Triple Systems and Labelings of Triangular Cacti|journal=Scientia|volume=1|pages=87–95|year=1988}}.

A graceful graph with edges 0 to {{mvar|m}} is conjectured to have no fewer than $\backslash left\backslash lceil\; \backslash sqrt\{3\; m+\backslash tfrac\{9\}\{4\}\}\; \backslash right\backslash rfloor$ 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 $3\; m^2$ edges, with the case for 6-valence shown below.

File:Toroidal6.png