Study on graceful labeling of trees

Abstract

A tree is a connected acyclic graph on n vertices and n����1 edges. Graceful labeling of a tree is a labeling of its vertices with the numbers from 0 to n����1, so that no two vertices share a label, labels of edges, being absolute difference of the labels of its end points, are also distinct. There is a famous conjecture named Graceful tree conjecture or Ringel-Kotzig Conjecture that says “All trees are graceful”. Almost 50-year old conjecture is yet to be proved. However, researchers have been able to prove that many classes of trees are graceful. In this thesis, we have proved that the classes of Superstar and Extended Superstarare graceful. A tree with one internal node and k leaves is said to be a star S1;k or a complete bipartite graph K1;k. Superstar is a tree that consists of several stars all connected to a single star by sharing their leaves. If we remove all the leaves of a Superstar then we will get a Spider tree which has already been proved to be graceful. Extended Superstar is a tree that consists of several Superstars all connected to a single star by sharing their leaves. We have also proved that extended superstars are graceful.