The extended metamorphosis of a complete bipartite design into a cycle system

A K-t,K-t-design of order n is an edge-disjoint decomposition of K-n into copies of K-t,K-t. When t is odd, an extended metamorphosis of a K-t,K-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 K-t,K-t block, and rearranging all the remaining 1-factors in each K-t,K-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 K-t,K-t block, rather than merely one subgraph. In this paper an extended metamorphosis of a K-t,K-t-design of order congruent to 1 (mod 4t(2)) into a 2t-cycle system of the same order is given for all odd t > 3. A metamorphosis of a 2-fold K-t,K-t-design of any order congruent to 1 (mod 4t(2)) 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 K-t,K-t is easily seen to contain t/2 edge-disjoint cycles of length 2t, and so the metamorphosis in that case is straightforward. (C) 2004 Elsevier B.V. All rights reserved.

Steiner triple systems with two disjoint subsystems

It is shown that there exists a triangle decomposition of the graph obtained from the complete graph of order v by removing the edges of two vertex disjoint complete subgraphs of orders u and w if and only if u, w, and v are odd, ((v)(2)) - ((u)(2)) - ((w)(2)) equivalent to 0 (mod 3), and v >= w + u + max {u, w}. Such decompositions are equivalent to group divisible designs with block size 3, one group of size u, one group of size w, and v - u - w groups of size 1. This result settles the existence problem for Steiner triple systems having two disjoint specified subsystems, thereby generalizing the well-known theorem of Doyen and Wilson on the existence of Steiner triple systems with a single specified subsystem. (c) 2005 Wiley Periodicals, Inc.