Formatted abstract

An embedding of a partial Gdesign (X, P) is a Gdesign (V, B) with the property that X C V and P C B. In 1976, R.M. Wilson [66] showed, among other things, that any partial Gdesign can be finitely embedded; however, the order of Wilson's embedding is exponentially large with respect to the order of the partial design. The problem of finding small embeddings of partial Gdesigns for various graphs G has received much attention in recent years, particularly for the case of partial Steiner triple systems and partial mcycle systems with m > 4. The work of Andersen, Hilton, Mendelsohn, Hoffman, Lindner, Rodger, Bryant and others has seen considerable progress made on this problem. In contrast to this, the search for even a polynomial embedding of partial (n, k, 1)BIBDs, for any given k > 4, has been unsuccessful. The closest result of interest to this problem is Hoffman and Lindner's 8n + 16√n + 82 embedding for partial (K_{4} \ K_{2})designs [26]. While the graph K_{4} \ K_{2} differs from K_{4} (a block of size 4) by only one edge, Hoffman and Lindner's embedding relies heavily on the fact that K_{4} \ K_{2} is tripartite. Since K_{4} is not tripartite, a small embedding for partial K_{4}designs (that is, partial (n, 4, 1) BIBDs) appears to be beyond the reach of the current methods. In this thesis, we consider the problem of finding small embeddings of partial Gdesigns for various graphs G, as well as several closely related problems. Given the attention the embedding problem has received for the case of cycles, the initial focus of this thesis is on constructing small embeddings for certain cyclerelated graphs G. In Chapter 2, we consider the case when G is either D_{6} (a diagonal cycle of order 6) or a (4, 1)kite; note that both of these graphs are bipartite and differ from an even cycle by only one edge. Chapter 3 presents an embedding of partial (m, k)kite designs for any given values of m and k. In Chapter 4, a technique is presented for obtaining a cubic embedding of a restricted class of partial K_{4}designs. This embedding is valid for any partial K_{4} design which has the property that every copy of K_{4} contains at least two vertices which do not occur in any other copy of K_{4}. The concept of irreducibility is introduced in Chapter 5, and is applied to 2 fold mcycle systems. Specifically, it is shown that for any pair of integers (m, n) with 4 < m < n, if there exists an mcycle system of order n, then there exists an irreducible 2fold mcycle system of order n, except when (m, n) = (5, 5). A similar result has already been established by Kramer [35] for the case of 3 cycles. Chapter 6 describes further results on irreducible λfold mcycle systems when λ> 2. We prove the existence of irreducible 3 fold mcycle systems of various orders, and show that for any λ > 2, there exists an irreducible Afold mcycle system of order n for a sufficiently large integer n. The problem of immersing partial Steiner triple systems is the focus of Chapter 7. An immersing of a partial Steiner triple system (V, P) of order n is a λfold triple system (V, B) of order n such that P C B. It is shown that a partial Steiner triple system of order n can always be immersed in a 6fold triple system of order n if n is odd, and a 12 fold triple system of order n if n is even. Finally, in Chapter 8 we turn our attention to pairs of orthogonal latin squares. Heinrich and Zhu [24] have shown that a pair of orthogonal latin squares of order n can be embedded in a pair of orthogonal latin squares of order t if t > 3n, the bound of 3n being best possible. Obtaining an analogous result for pairs of partial orthogonal latin squares has proved to be an extremely challenging problem. Although Lindner has proved that a pair of partial orthogonal latin squares can always be finitely embedded, there is no known method which obtains an embedding of polynomial order (with respect to the order of the partial arrays). The less difficult problem of embedding a single partial latin square in a pair of orthogonal latin squares is investigated in this chapter.
