Cycle decompositions of generalised complete graphs

Benjamin R. Smith
Supervisors: Elizabeth Billington and Nicholas Cavenagh


Well-known necessary conditions for a graph $G$ to admit a decomposition
into cycles of length $k$ are that (i) $G$ has at least $k$ vertices;
(ii) $G$ is even; and (iii) the total number of edges in $G$ is a
multiple of $k$. In the case that $G\cong K_n$, the complete graph on
$n$ vertices, these conditions are known to be sufficient. In this talk
we discuss the conjecture that conditions (i), (ii) and (iii) are also
sufficient in the cases where $G\cong \lambda K_n$, the $\lambda$-fold
complete multigraph on $n$ vertices; and $G\cong K_n\ast\overline{K}_m$,
the complete equipartite graph having $n$ parts of size $m.