Graceful labeling

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
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 between 0 and 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, which hypothesizes that all trees are graceful. It is still an open conjecture, although a related but slightly weaker conjecture known as Ringel's conjecture was proven true in 2020.[3][4][5] The Ringel–Kotzig conjecture is also known as the "graceful labeling conjecture". Kotzig once called the effort to prove the conjecture a "disease".[6]

Another weaker version of graceful labelling is the near graceful labeling, in which the vertices can be labeled using some subset of the integers between 0 and m+1 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+1 inclusive.

Another conjecture in graph theory is the Rosa's Conjecture, named after Alexander Rosa, which says that all triangular cacti are graceful or nearly-graceful.[7]

Selected results[edit]

See also[edit]

External links[edit]

References[edit]

  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. ^ Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny (2020). "A proof of Ringel's Conjecture". arXiv:2001.02665 [math.CO].
  4. ^ Huang, C.; Kotzig, A.; Rosa, A. (1982), "Further results on tree labellings", Utilitas Mathematica, 21: 31–48, MR 0668845.
  5. ^ Hartnett, Kevin. "Rainbow Proof Shows Graphs Have Uniform Parts". Quanta Magazine. Retrieved 2020-02-29.
  6. ^ Huang, C.; Kotzig, A.; Rosa, A. (1982), "Further results on tree labellings", Utilitas Mathematica, 21: 31–48, MR 0668845.
  7. ^ Rosa, A. (1988), "Cyclic Steiner Triple Systems and Labelings of Triangular Cacti", Scientia, 1: 87–95.
  8. ^ 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.
  9. ^ 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.
  10. ^ 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.
  11. ^ Horton, Michael P. (2003), Graceful Trees: Statistics and Algorithms.
  12. ^ Fang, Wenjie (2010), A Computational Approach to the Graceful Tree Conjecture, arXiv:1003.3045, Bibcode:2010arXiv1003.3045F. See also Graceful Tree Verification Project
  13. ^ 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.
  14. ^ Weisstein, Eric W. "Graceful graph". MathWorld.

Further reading[edit]

  • (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