ON ALGORITHMIC GRAPH THEORY GRAPH LABELLING ALGORITHMS

Abstract

The problem of this thesis is the graceful I labeling of graphs, in particular, the graceful la.beling

of trees. In other1 words: Is every tree graceful?.

We prove the gracefulness of some special ' cases of trees,such as the star, the path, and a generalized star. We study two cases of the generalized star. The first is a generalized star in which all branchs are equal, and the second case is a generalized star in which all branches execpt one have 1 the same length. We prove the gracefulness of the generalized star: in both cases. Finally, we suggest an algorithm to check whether a tree is graceful or not . Also, we sugget another algorithm to generate all trees with a given number of vertices . I We suggest further algorithm to generate trees

of order n+ 1 by knowing the diagrams of trees of order