Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650767 | Discrete Mathematics | 2008 | 19 Pages |
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 Kn(m)Kn(m) (with n⩾4n⩾4 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, Kn(m),tKn(m),t, having n parts of size m and one part of size t , has a gregarious 4-cycle decomposition if and only if (i) n⩾3n⩾3, (ii) t⩽⌊m(n-1)/2⌋t⩽⌊m(n-1)/2⌋ and (iii) a 4-cycle decomposition exists, that is, either m and t are even or else m and t are both odd and n≡0(mod8).