Search

In this paper we show that the complete equipartite graph with n parts, each of size 2k, decomposes into cycles of length λ2 for any even n≥4, any integer k≥3 and any odd λ such that 3≤λ

In this article we find necessary and sufficient conditions to decompose a complete equipartite graph into cycles of uniform length, in the case that the length is both even and short relative to the number of parts. (C) 2010 Wiley Periodicals, Inc. J Combin Designs 19: 131-143, 2011

In this article, we introduce a new technique for obtaining cycle decompositions of complete equipartite graphs from cycle decompositions of related multigraphs. We use this technique to prove that if n, m and 2 are positive integers with n >= 3, lambda >= 3 and n and lambda both odd, then the complete equipartite graph having n parts of size m admits a decomposition into cycles of length lambda(2) whenever nm >= lambda(2) and lambda divides m. As a corollary, we obtain necessary and sufficient conditions for the decomposition of any complete equipartite graph into cycles of length p2, where p is prime. (C) 2010 Wiley Periodicals, Inc. J Combin Designs 18: 401-414, 2010

In 1998 Cavenagh [N.J. Cavenagh, Decompositions of complete tripartite graphs into k-cycles, Australas. J. Combin. 18 (1998) 193-200] gave necessary and sufficient conditions for the existence of an edge-disjoint decomposition of a complete equipartite graph with three parts, into cycles of some fixed length k. Here we extend this to paths, and show that such a complete equipartite graph with three partite sets of size m, has an edge-disjoint decomposition into paths of length k if and only if k divides 3m^2 and k =3 if and only if k divides 10m^2 and k=

It is an open problem to determine whether a complete equipartite graph K-m * (K) over bar (n) (having m parts of size n) admits a decomposition into cycles of arbitrary fixed length k whenever m, n, and k satisfy the obvious necessary conditions for the existence of such a decomposition. Recently, Manikandan and Paulraja [6] have shown the necessary conditions are indeed sufficient for a decomposition into cycles of length p where p > 5 is a prime. The case p = 3 was settled by Hanani [4] and the case p = 5 was settled by Billington et al. [2]. Here, we extend this result and show that the necessary conditions for the decomposition of K-m * (K) over bar (n) into cycles of length 2p (where p >= 3 is a prime) are also sufficient. (c) 2007 Wiley Periodicals, Inc.

A k-cycle decomposition of a complete multipartite graph is said to be gregarious if each k-cycle in the decomposition has its vertices in k different partite sets. Equipartite 3-cycle systems are 3-GDDs (and so are automatically gregarious), and necessary and sufficient conditions for their existence are known. The cases of equipartite gregarious 4-, 6- and 8-cycle systems have also been dealt with (using techniques that could be applied in the case of any even length cycle). Here we give necessary and sufficient conditions for the existence of a gregarious 5-cycle decomposition of the complete equipartite graph Km(n) (in effect the first odd length cycle case for which the gregarious constraint has real meaning). In doing so, we also define some general cyclic constructions for the decomposition of certain complete equipartite graphs into gregarious p-cycles (where p is an odd prime).

A k-cycle decomposition of a complete multipartite graph is said to be gregarious if each k-cycle in the decomposition has its vertices in k different partite sets. Equipartite gregarious 3-cycle systems are 3-GDDs, and necessary and sufficient conditions for their existence are known (see for instance the CRC Handbook of Combinatorial Designs, 1996, C.J. Colbourn, J.H. Dinitz (Eds.), Section III 1.3). The cases of equipartite and of almost equipartite 4-cycle systems were recently dealt with by Billington and Hoffman. Here, for both 6-cycles and for 8-cycles, we give necessary and sufficient conditions for existence of a gregarious cycle decomposition of the complete equipartite graph K"n"("a") (with n parts, n>=6 or n>=8, of size a).

In this paper we examine the problem of decomposing the lexicographic product of a cycle with an empty graph into cycles of uniform length. We determine necessary and sufficient conditions for a solution to this problem when the cycles are of odd length. We apply this result to find necessary and sufficient conditions to decompose a complete equipartite graph into cycles of uniform length, in the case that the length is both odd and short relative to the number of parts.

A $k$-cycle decomposition of a multipartite graph $G$ is said to be gregarious if each $k$-cycle in the decomposition intersects $k$ distinct partite sets of $G$. In this paper we prove necessary and sufficient conditions for the existence of such a decomposition in the case where $G$ is the complete equipartite graph, having $n$ parts of size $m$, and either $n\equiv 0,1\pmod{k}$, or $k$ is odd and $m\equiv 0\pmod{k}$. As a consequence, we prove necessary and sufficient conditions for decomposing complete equipartite graphs into gregarious cycles of prime length.