Search

Abstract: Let denote a twofold -cycle system with an even number of cycles. If these -cycles can be paired together so that: (i) each pair contains a common edge; (ii) removal of the repeated common edge from each pair leaves a -cycle; (iii) all the repeated edges, once removed, can be rearranged exactly into a collection of further -cycles; then this is a metamorphosis of a twofold -cycle system into a twofold -cycle system. The existence of such metamorphoses has been dealt with for the case of 3-cycles (Gionfriddo and Lindner, 2003) and 4-cycles (Yazıcı, 2005) . If a twofold -cycle system of order exists, which has not just one but has different metamorphoses, from different pairings of its cycles, into twofold -cycle systems, such that the collection of all removed double edges from all metamorphoses precisely covers , we call this a complete set of twofold paired -cycle metamorphoses into twofold -cycle systems. In this paper, we show that there exists a twofold 4-cycle system of order with a complete set of metamorphoses into twofold 6-cycle systems if and only if (mod 24), . [Copyright &y& Elsevier]

Abstract: A 6-cycle system of a graph is an edge-disjoint decomposition of into 6-cycles. Graphs , for which necessary and sufficient conditions for existence of a 6-cycle system have been found, include complete graphs and complete equipartite graphs. A 6-cycle system of is said to be 2-perfect if the graph formed by joining all vertices distance 2 apart in the 6-cycles is again an edge-disjoint decomposition of , this time into 3-cycles, since the distance 2 graph in any 6-cycle is a pair of disjoint 3-cycles. Necessary and sufficient conditions for existence of 2-perfect 6-cycle systems of both complete graphs and complete equipartite graphs are known, and also of -fold complete graphs. In this paper, we complete the problem, giving necessary and sufficient conditions for existence of -fold 2-perfect 6-cycle systems of complete equipartite graphs. [Copyright &y& Elsevier]

Abstract: In 1998 Cavenagh [N.J. Cavenagh, Decompositions of complete tripartite graphs into -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 . Here we extend this to paths, and show that such a complete equipartite graph with three partite sets of size , has an edge-disjoint decomposition into paths of length if and only if divides and . Further, extending to five partite sets, we show that a complete equipartite graph with five partite sets of size has an edge-disjoint decomposition into cycles (and also into paths) of length with if and only if divides and for cycles (or for paths). [Copyright &y& Elsevier]

Abstract: We show that a complete equipartite graph with four partite sets has an edge-disjoint decomposition into cycles of length if and only if , the partite set size is even, divides the number of edges in the equipartite graph and the total number of vertices in the graph is at least . We also show that a complete equipartite graph with four even partite sets has an edge-disjoint decomposition into paths with edges if and only if divides the number of edges in the equipartite graph and the total number of vertices in the graph is at least . [Copyright &y& Elsevier]

Abstract: The complete multipartite graph with n parts of size m is shown to have a decomposition into n-cycles in such a way that each cycle meets each part of ; that is, each cycle is said to be gregarious. Furthermore, gregarious decompositions are given which are also resolvable. [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]

The trade spectrum of a graph G is essentially the set of all integers t for which there is a graph H whose edges can be partitioned into t copies of G in two entirely different ways. In this paper we determine the trade spectrum of complete partite graphs, in all but a few cases. [Copyright &y& Elsevier]