Cycle systems: an investigation of colouring and invariants

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.