Article ID Journal Published Year Pages File Type
4650767 Discrete Mathematics 2008 19 Pages PDF
Abstract

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).

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,