Cycle systems: an investigation of colouring and invariants

Burgess, Andrea (2005) Cycle systems: an investigation of colouring and invariants. Masters thesis, Memorial University of Newfoundland.

[img] [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.

Download (16MB)

Abstract

An m-cycle system of order n is a partition of the edges of the complete graph Kn into m-cycles. This thesis explores two aspects of cycle systems: colouring of cycle systems and invariants for cycle systems. -- A weak k-colouring of an m-cycle system of order n is a partition of the vertices of Kn into k colour classes such that the vertices of no m-cycle are all of the same colour. The smallest value of k for which a cycle systemS admits a weak k-colouring is called the chromatic number of S. We study weak colourings of even cycle systems, and show that for any integers k ≥ 2 and r ≥ 2, there is a k-chromatic (2r)-cycle system. -- An invariant for an m-cycle system is a function I such that I(S) = I(S') for any m-cycle systems S and S' which are isomorphic. We examine the utility of various invariants in distinguishing nonisomorphic cycle systems and enumerate all pairwise nonisomorphic 11-cycle systems of order 11.

Item Type: Thesis (Masters)
URI: http://research.library.mun.ca/id/eprint/10227
Item ID: 10227
Additional Information: Bibliography: leaves 78-83.
Department(s): Science, Faculty of > Mathematics and Statistics
Date: 2005
Date Type: Submission
Library of Congress Subject Heading: Block designs; Graph coloring; Invariants; Paths and cycles (Graph theory)

Actions (login required)

View Item View Item

Downloads

Downloads per month over the past year

View more statistics