Some Classes of Graphs Known to be Graceful

Graceful labeling graphs were popularized in 1967 by Alex Rosa called a function f a β - valuation of a graph G with m edges if f is an injection from the vertices of a graph G to the set {0, 1, …,m} such that, when each edge xy is assigned the label |f(x) - f(y)|, the resulting edge labels are distinct. We call a graph" graceful" if such an f exists. It is still not known, if every tree has a graceful labeling. This was conjectured by Rosa at International Symposium in Rome in July 1966. Since that time, there was lot of attempts to prove (and few to disprove) this conjecture, but there are still just very few classes of trees, which are proved to be graceful. In this paper we present some classes of trees known to be graceful.