Equipartite and almost-equipartite gregarious 4-cycle systems Original Research Article

A 4-cycle decomposition of a complete multipartite graph is said to be gregarious if each 4-cycle in the decomposition has its vertices in four different partite sets. Here we exhibit gregarious 4-cycle decompositions of the complete equipartite graph image (with image parts of size m) whenever a 4-cycle decomposition (gregarious or not) is possible, and also of a complete multipartite graph in which all parts but one have the same size. The latter complete multipartite graph, image, having n parts of size m and one part of size t, has a gregarious 4-cycle decomposition if and only if (i) image, (ii) image and (iii) a 4-cycle decomposition exists, that is, either m and t are even or else m and t are both odd and image.