Cycle and closed trail decompositions of complete equipartite graphs and complete multigraphs

Abstract

An H-decomposition of a graph G is a partition of the edges of G into subsets, each of which induces a graph isomorphic to H. In this thesis, we will study decompositions of certain graphs into cycles and closed trails. In particular, we consider decompositions of complete multigraphs and complete equipartite graphs. The complete multigraph lambdaKm is the multigraph with m vertices and lambda edges between each pair of vertices. The complete equipartite graph Km * Kn with m parts of size n is the simple graph on mn vertices, such that the vertices are partitioned into m parts of size n, and two vertices are adjacent if and only if they are in different parts. With regard to closed trail decompositions, we find necessary and sufficient conditions for the existence of a decomposition of the complete equipartite graph Km * Kn into closed trails of length k. We then turn our attention to cycle decompositions, and give necessary and sufficient conditions for the existence of a decomposition of the complete multigraph 3 Km into cycles of odd length k ≠ 9. We then show how to use this result to construct k-cycle decompositions of Km * K3 when k = 9k', where k'| &parl0;m2&parr0; and k' > 3. In addition, we discuss other cases in which decompositions of Km * K3 into k-cycles can be found.