DECOMPOSITIONS OF GENERALIZED COMPLETE GRAPHS

A decomposition of a graph G is a collection of edge-disjoint subgraphs of G whose edges partition the edges of G. In the case where each of these subgraphs is isomorphic to some graph H, we say that G admits a decomposition into H. The problem of determining whether a given graph G admits a decomposition into a given graph H is the primary focus of this thesis. In particular, we are concerned with those cases in which H is a cycle. Obvious necessary conditions for a graph G (having nonempty edge set) to admit a decomposition into cycles of length k are that: (i) G contains at least k vertices; (ii) every vertex in G has even degree; and (iii) the total number of edges in G is a multiple of the cycle length k. Recent papers by Alspach and Gavlas and Sajna have shown that these three necessary conditions are sufficient in the case where G is either K2+1 (the complete graph of odd order), or K2 − F (the complete graph of even order minus a 1-factor). In this thesis we examine whether conditions (i), (ii) and (iii) above are also sufficient when G is one of λK (the λ-fold complete multigraph), K ∗ K (the complete equipartite graph having parts of size ) or λK ∗ K (the λ-fold complete equipartite graph).