Decomposing Complete Equipartite Graphs into Short Odd Cycles

  • Benjamin R. Smith
  • Nicholas J. Cavenagh


In this paper we examine the problem of decomposing the lexicographic product of a cycle with an empty graph into cycles of uniform length. We determine necessary and sufficient conditions for a solution to this problem when the cycles are of odd length. We apply this result to find necessary and sufficient conditions to decompose a complete equipartite graph into cycles of uniform length, in the case that the length is both odd and short relative to the number of parts.

Article Number