Gracefully labelled trees from Skolem and related sequences

Abstract

In this thesis we use Skolem sequences, hooked Skolem sequences, and periodic odd sequences to find graceful labellings of trees. -- Using a particular Skolem sequence of order n we will produce a graceful labelling of a certain tree on 2n vertices. Additionally, the following two theorems will be established. -- • A Skolem sequence of order n ≡ 0,1 (mod 4) implies the existence of a graceful tree on 2n vertices which has a perfect matching or a matching on 2n - 2 vertices -- • A hooked Skolem sequence of order n ≡ 2,3 (mod 4) implies the existence of a graceful tree on 2n +1 vertices which has a matching on either 2n or 2n - 2 vertices. -- The periodic odd sequence will be used to show a particular class of trees to be graceful. Given a tree T, consider one of its longest paths PT, which is not necessarily unique. We define T to be m-distant if no vertices of T are a distance greater than m away from PT. We will show that all 3-distant graphs with the following properties are graceful. -- (1) They have perfect matchings. -- (2) They can be constructed by the attachment of paths of length two to the vertices of a 1-distant tree (caterpillar), by identifying an end vertex of each path with a vertex of the 1-distant tree. Consequently, all 2-distant trees (lobsters) having perfect matchings are graceful.