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

作者：Smith Benjamin R; Cavenagh Nicholas^*

来源：Discrete Mathematics, 2012, 312(10): 1611-1622.

DOI：10.1016/j.disc.2012.02.010

• Graph decomposition
• Cycle decomposition
• Complete equipartite graph

In this paper we show that the complete equipartite graph with n parts, each of size 2k, decomposes into cycles of length lambda(2) for any even n %26gt;= 4, any integer k %26gt;= 3 and any odd lambda such that 3 %26lt;= lambda %26lt; root 2nk and lambda divides k. As a corollary, we obtain necessary and sufficient conditions for the decomposition of any complete equipartite graph with an even number of parts into cycles of length p(2), where p is prime. In proving our main result, we have also shown the following. Let lambda %26gt;= 3 and n %26gt;= 4 be odd and even integers, respectively. Then there exists a decomposition of the lambda-fold complete equipartite graph with n parts, each of size 2k, into cycles of length A if and only if lambda %26lt; 2kn. In particular, if we take the complete graph on 2n vertices, remove a 1-factor, then increase the multiplicity of each edge to lambda. the resultant graph decomposes into cycles of length lambda if and only if lambda %26lt; 2n.

• 出版日期2012-5-28