Kalpana Kalpana (Editor)

Graceful labeling

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Graceful labeling

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 such that each edge is uniquely identified by the positive, or absolute difference between its endpoints. A graph which admits a graceful labeling is called a graceful graph.

Contents

The name "graceful labeling" is due to Solomon W. Golomb; this class of labelings was originally given the name β-labelings by Alexander Rosa in a 1967 paper on graph labelings.

A major unproven 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. The Ringel-Kotzig conjecture is also known as the "graceful labeling conjecture". Kotzig once called the effort to prove the conjecture a "disease".

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) can't 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 graphs and caterpillar graphs are graceful.
  • All lobster graphs with a perfect matching are graceful.
  • All trees with at most 29 vertices are graceful; this result was shown by Michael Horton in his Honours thesis in 2003.
  • All trees with at most 27 vertices are graceful; this result was shown by Aldred and McKay in 1998 using a computer program. An extension of this (using a different computational method) up to trees with 35 vertices was claimed in 2010 by the Graceful Tree Verification Project, a distributed computing project led by Wenjie Fang.
  • All wheel graphs, web graphs, helm graphs, gear graphs, and rectangular grids are graceful.
  • All n-dimensional hypercubes are graceful.
  • All simple graphs with four or fewer vertices are graceful. The only non-graceful simple graphs with five vertices are the 5-cycle (pentagon); the complete graph K5; and the butterfly graph.

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

    • References

    Graceful labeling Wikipedia
    (Text) CC BY-SA