# Graceful labeling

A graceful labeling. Vertex labels are in black, edge labels in red.

In graph theory, a graceful labeling of a graph with m edges is a labeling of its vertices with some subset of the integers from 0 to 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 m inclusive.[1] 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.[2]

A major conjecture in graph theory is the graceful tree conjecture or Ringel–Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, and sometimes abbreviated GTC.[3] 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.[4][5][6] Kotzig once called the effort to prove the conjecture a "disease".[7]

Another weaker version of graceful labelling is near-graceful labeling, in which the vertices can be labeled using some subset of the integers on [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 [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.[8]

A graceful graph with edges 0 to m is conjectured to have no fewer than ${\displaystyle \left\lceil {\sqrt {3m+{\tfrac {9}{4}}}}\right\rfloor }$ vertices, due to sparse ruler results. This conjecture has been verified for all graphs with 213 or fewer edges.

A graceful graph with 27 edges and 9 vertices

## References

1. ^ Virginia Vassilevska, "Coding and Graceful Labeling of trees." SURF 2001. PostScript
2. ^ a b Rosa, A. (1967), "On certain valuations of the vertices of a graph", Theory of Graphs (Internat. Sympos., Rome, 1966), New York: Gordon and Breach, pp. 349–355, MR 0223271.
3. ^ Wang, Tao-Ming; Yang, Cheng-Chang; Hsu, Lih-Hsing; Cheng, Eddie (2015), "Infinitely many equivalent versions of the graceful tree conjecture", Applicable Analysis and Discrete Mathematics, 9 (1): 1–12, doi:10.2298/AADM141009017W, MR 3362693
4. ^ Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny (2020). "A proof of Ringel's Conjecture". arXiv:2001.02665 [math.CO].
5. ^ Huang, C.; Kotzig, A.; Rosa, A. (1982), "Further results on tree labellings", Utilitas Mathematica, 21: 31–48, MR 0668845.
6. ^ Hartnett, Kevin. "Rainbow Proof Shows Graphs Have Uniform Parts". Quanta Magazine. Retrieved 2020-02-29.
7. ^ Huang, C.; Kotzig, A.; Rosa, A. (1982), "Further results on tree labellings", Utilitas Mathematica, 21: 31–48, MR 0668845.
8. ^ Rosa, A. (1988), "Cyclic Steiner Triple Systems and Labelings of Triangular Cacti", Scientia, 1: 87–95.
9. ^ Morgan, David (2008), "All lobsters with perfect matchings are graceful", Bulletin of the Institute of Combinatorics and Its Applications, 53: 82–85, hdl:10402/era.26923.
10. ^ a b Gallian, Joseph A. (1998), "A dynamic survey of graph labeling", Electronic Journal of Combinatorics, 5: Dynamic Survey 6, 43 pp. (389 pp. in 18th ed.) (electronic), MR 1668059.
11. ^ Aldred, R. E. L.; McKay, Brendan D. (1998), "Graceful and harmonious labellings of trees", Bulletin of the Institute of Combinatorics and Its Applications, 23: 69–72, MR 1621760.
12. ^
13. ^ Fang, Wenjie (2010), A Computational Approach to the Graceful Tree Conjecture, arXiv:1003.3045, Bibcode:2010arXiv1003.3045F. See also Graceful Tree Verification Project
14. ^ Kotzig, Anton (1981), "Decompositions of complete graphs into isomorphic cubes", Journal of Combinatorial Theory, Series B, 31 (3): 292–296, doi:10.1016/0095-8956(81)90031-9, MR 0638285.
15. ^