Premium
Decomposing complete equipartite graphs into odd square‐length cycles: number of parts odd
Author(s) -
Smith Benjamin R.
Publication year - 2010
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.20268
Subject(s) - mathematics , combinatorics , corollary , graph , square (algebra) , prime (order theory) , decomposition , discrete mathematics , geometry , ecology , biology
In this article, we introduce a new technique for obtaining cycledecompositions 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