Search

We establish necessary and sufficient conditions for the existence of a decomposition of a complete multigraph into edge-disjoint cycles of specified lengths, or into edge-disjoint cycles of specified lengths and a perfect matching.

Suppose M=m1,m2,.,mr and N=n1,n2,.,nt are arbitrary lists of positive integers. In this article, we determine necessary and sufficient conditions on M and N for the existence of a simple graph G, which admits a face 2-colorable planar embedding in which the faces of one color have boundary lengths m1,m2,.,mr and the faces of the other color have boundary lengths n1,n2,.,nt. Such a graph is said to have a planar (M;N)-biembedding. We also determine necessary and sufficient conditions on M and N for the existence of a simple graph G whose edge set can be partitioned into r cycles of lengths m1,m2,.,mr and also into t cycles of lengths n1,n2,.,nt. Such a graph is said to be (M;N)-decomposable.

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 paper we establish necessary and sufficient conditions for decomposing the complete multigraph lambda K(n) into cycles of length lambda, and the lambda-fold complete symmetric digraph lambda K(n)*, into directed cycles of length lambda. As a corollary to these results we obtain necessary and sufficient conditions for decomposing lambda K(n), (respectively, lambda K(n)*) into cycles (respectively, directed cycles) of prime length. (C) 2009 Wiley Periodicals, Inc. J Combin Designs 18: 85-93, 2010

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

Necessary conditions for a simple connected graph G to admit a decomposition into closed trails of length k ≥ 3 are that G is even and its total number of edges is a multiple of k. In this paper we show that these conditions are sufficient in the case when G is the complete equipartite graph having at least three parts, each of the same size.

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

A decomposition of a graph G is a collection of edge-disjoint subgraphs of G whose edges partition the edges of G. In the case where each of these subgraphs is isomorphic to some graph H, we say that G admits a decomposition into H. The problem of determining whether a given graph G admits a decomposition into a given graph H is the primary focus of this thesis. In particular, we are concerned with those cases in which H is a cycle. Obvious necessary conditions for a graph G (having nonempty edge set) to admit a decomposition into cycles of length k are that: (i) G contains at least k vertices; (ii) every vertex in G has even degree; and (iii) the total number of edges in G is a multiple of the cycle length k. Recent papers by Alspach and Gavlas and Sajna have shown that these three necessary conditions are sufficient in the case where G is either K2+1 (the complete graph of odd order), or K2 − F (the complete graph of even order minus a 1-factor). In this thesis we examine whether conditions (i), (ii) and (iii) above are also sufficient when G is one of λK (the λ-fold complete multigraph), K ∗ K (the complete equipartite graph having parts of size ) or λK ∗ K (the λ-fold complete equipartite graph).

We prove that any complete multipartite graph with parts of even size can be decomposed into closed trails with prescribed even lengths., NA

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.