Gracefully labelled trees from Skolem and related sequences

Morgan, David (2001) Gracefully labelled trees from Skolem and related sequences. Masters thesis, Memorial University of Newfoundland.

[English] PDF (Migrated (PDF/A Conversion) from original format: (application/pdf)) - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (5MB) [English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. (Original Version)

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.

Actions (login required)

View Item