Gracefull Skinny Lobster

A graceful labeling of a graph is an injective mapping from the set of its vertices to the set {1, 2,...,m+1}, where m is the number of edges in the graph, such that each edge receives the absolute difference of the labels of its endpoints as an edge-label and such that all edges receive distinct edge-labels. It was conjectured back in 1960's that all trees can be gracefully labeled. This conjecture is called the graceful tree conjecture. The graceful tree conjecture is motivated by another famous conjecture by Ringel that given a tree on m edges, complete graph K2m+1 can be decomposed into 2m+ 1 copies of that tree. The graceful tree conjecture is important because resolving it leads to the resolution of Ringel's conjecture. This thesis undertakes the graceful labeling of certain kind of trees that belong to a well-known family of trees called lobsters; we refer to this family as skinny lobsters. In this thesis we prove that skinny lobsters are graceful