DSpace JSPUI

In this thesis, we first observe that a lobster with diameter at least five has a unique path H = x0, x1, . . . , xm with the property that, besides the adjacencies in H, both x0 and xm are adjacent to the centers of at least one K1,s, where s > 0, and each xi, 1 ≤ i ≤ m− 1, is at most adjacent to the centers of some K1,s, where s ≥ 0. This unique path H is called the central path of the lobster. We call K1,s an even branch if s is nonzero even, an odd branch if s is odd, and a pendant branch if s= 0. In 1979, Bermond [7] conjectured that “all lobsters are graceful” as a special case of the graceful tree conjecture [59], [54] which states that “all trees are graceful”. Bermond’s conjecture is unsolved till date. Prior to our work, Ng [48], Wang et al. [58], Chen et al. [21], and Morgan [44] have given graceful labelings to some classes of lobsters. In this thesis we give graceful labelings to several classes of lobsters. In the initial few chapters of the thesis we are inspired by the results in [58]. Wang et al. have given graceful labelings to lobsters in which the vertex x0 is attached to an odd number (≥ 3)of branches and each of the remaining vertices of the central path is attached to an even number of branches, which is shared by the lobsters appear in Chapters 3 through 5. However, in the lobsters of [58] only one type of, i.e. odd (or even) branches, are incident on the vertices of the central path, whereas in the lobsters of Chapters 3 through 5, the number of branches incident on x0 may be any odd and the branches incident on xi, 0 ≤ i ≤ m may be of the same type, any two types, or all three types of certain combinations. Further, using component moving and inverse transformation we give three general graceful constructions to generate graceful trees from a graceful tree of certain type. When we apply these constructions on diameter four trees we get graceful lobsters.