%0 Journal Article
%T New Classes of Graceful Trees
%A Md. Forhad Hossain
%A Md. Momin Al Aziz
%A M. Kaykobad
%J Journal of Discrete Mathematics
%D 2014
%I Hindawi Publishing Corporation
%R 10.1155/2014/194759
%X Graceful labeling is one of the most researched problems. One of the earliest results is that caterpillars are graceful. We show that caterpillars connected to a vertex recursively satisfying certain conditions are also graceful. 1. Introduction Let be any arbitrary tree on edges. If its vertices can be distinctly labeled using integers so that all the induced edge labels (vertices labeled and induce label on edge ) are also distinct, then the labeling is called graceful. It was conjectured that all trees are graceful. This has connection with RingelĄ¯s conjecture and some related results can be found in [1, 2]; Kotzig later conjectured that such a decomposition could be achieved cyclically. Rosa [2] established that these conjectures could be solved by showing that every tree is graceful. The conjecture has been very widely studied and new classes of trees have been proved to be graceful (see [3¨C5]). However, it has not been possible to devise a single algorithm to stand out against the conjecture for any arbitrary tree. The research has continued in two directions: newer and more generalized classes of graceful trees are discovered [6¨C8] or graceful labeling has been computed for all larger trees up to a fixed order. Computationally, it has been shown so far that all trees with up to 35 vertices are graceful [9]. Graceful labeling has found useful applications in coding theory, X-ray crystallography, radar, astronomy, circuit design, communication network addressing, and database management (see [10, 11]). In Section 2, we define the classes of trees that have already been proved graceful and critical to our work. Section 3 defines our work of two new classes of trees that have been proved graceful. 2. Gracefully Labeled Trees Let us introduce the classes of trees for which graceful labeling has been found. A path is a tree with only two leaves. A caterpillar is a tree such that if all leaves are removed, the remaining graph is a path. This path can be termed as backbone of the caterpillar. Rosa [12] proved that all caterpillars are graceful. In Figure 1, a gracefully labeled caterpillar has been shown. A caterpillar is labeled from one end of its backbone with . Its adjacent vertices are labeled using so far unused largest labels in such a way that vertices on the path get alternately the largest and smallest labels. In this way, while we label vertices the largest unused edge labels are generated. It may be noted that for an -edge tree if is a graceful labeling, then so is . So we can label any end of a caterpillar by or by . Figure 1: An example of
%U http://www.hindawi.com/journals/jdm/2014/194759/