Search

Abstract: Let denote the graph on a vertices with edges between every pair of vertices. Take p copies of this graph , and join each pair of vertices in different copies with edges. The resulting graph is denoted by , a graph that was of particular interest to Bose and Shimamoto in their study of group divisible designs with two associate classes. The existence of z-cycle decompositions of this graph have been found when . In this paper we consider resolvable decompositions, finding necessary and sufficient conditions for a 4-cycle factorization of (when is even) or of minus a 1-factor (when is odd) whenever a is even. [Copyright &y& Elsevier]

Abstract: 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 (with n parts, or , of size a). [Copyright &y& Elsevier]

A maximum packing of any λ-fold complete multipartite graph (where there are λ edges between any two vertices in different parts) with edge-disjoint 4-cycles is obtained and the size of each minimum leave is given. Moreover, when λ=2, maximum 4-cycle packings are found for all possible leaves. [ABSTRACT FROM AUTHOR]

A Kt,t-design of order n is an edge-disjoint decomposition of Kn into copies of Kt,t. When t is odd, an extended metamorphosis of a Kt,t-design of order n into a 2t-cycle system of order n is obtained by taking (t-1)/2 edge-disjoint cycles of length 2t from each Kt,t block, and rearranging all the remaining 1-factors in each Kt,t block into further 2t-cycles. The ‘extended’ refers to the fact that as many subgraphs isomorphic to a 2t-cycle as possible are removed from each Kt,t block, rather than merely one subgraph.In this paper an extended metamorphosis of a Kt,t-design of order congruent to 1 (mod 4t2) into a 2t-cycle system of the same order is given for all odd t>3. A metamorphosis of a 2-fold Kt,t-design of any order congruent to 1 (mod t2) into a 2t-cycle system of the same order is also given, for all odd t>3. (The case t=3 appeared in Ars Combin. 64 (2002) 65–80.)When t is even, the graph Kt,t is easily seen to contain t/2 edge-disjoint cycles of length 2t, and so the metamorphosis in that case is straightforward. [Copyright &y& Elsevier]

A 4-cycle in a tripartite graph with vertex partition {V1,V2,V3} is said to be gregarious if it has at least one vertex in each Vi, 1⩽i⩽3. In this paper, necessary and sufficient conditions are given for the existence of an edge-disjoint decomposition of any complete tripartite graph into gregarious 4-cycles. [Copyright &y& Elsevier]