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.

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

Actions (login required)

View Item