Equipartite and almost-equipartite gregarious 4-cycle systems (Q2470435): Difference between revisions

A \(4\)-cycle decomposition of a complete multipartite graph is gregarious if each \(4\)-cycle in the decomposition has its vertices in different partite sets. It is proved that there is a gregarious \(4\)-cycle decomposition of the complete multipartite graph \(K_{n(m)}\) having \(n\) parts of size \(m\) if and only if \(n \geq 4\) and (i) \(m\) is even, or (ii) \(m\) is odd and \(n \equiv 1\) mod \(8\). It is also shown that if \(a\) and \(b\) are even, a gregarious \(4\)-cycle decomposition exists for \(K_{n(a), b}\), a complete multipartite graph with \(n\) parts of size \(a\) and one of size \(b\), if and only if \(n \geq 4\) and \(b \leq \lfloor a(n-1)/2 \rfloor\), or \(n = 3\) and \(a = b\). Partial results are obtained when \(a\) and \(b\) are both odd.