Decomposing complete equipartite graphs into odd square-length cycles: number of parts odd

✍ Scribed by Benjamin R. Smith

• Publisher: John Wiley and Sons
• Year: 2010
• Tongue: English
• Weight: 155 KB
• Volume: 18
• Category: Article
• ISSN: 1063-8539
• DOI: 10.1002/jcd.20268

✦ Synopsis

Abstract

In this article, we introduce a new technique for obtaining cycle
decompositions of complete equipartite graphs from cycle decompositions of related multigraphs. We use this technique to prove that if n, m and λ are positive integers with n ≥ 3, λ≥ 3 and n and λ both odd, then the complete equipartite graph having n parts of size m admits a
decomposition into cycles of length λ^2^ whenever nm ≥ λ^2^ and λ divides m. As a corollary, we obtain necessary and sufficient conditions for the decomposition of any complete equipartite graph into cycles of length p^2^, where p is prime. © 2010 Wiley Periodicals, Inc. J Combin Designs 18:401‐414, 2010