Partial Graph Design Embeddings and Related Problems

Jenkins, Peter (2005). Partial Graph Design Embeddings and Related Problems PhD Thesis, School of Physical Sciences, The University of Queensland.

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
THE18945.pdf Full Text application/pdf 4.35MB 1
Author Jenkins, Peter
Thesis Title Partial Graph Design Embeddings and Related Problems
School, Centre or Institute School of Physical Sciences
Institution The University of Queensland
Publication date 2005
Thesis type PhD Thesis
Supervisor Elizabeth Billington
Peter Adams
Darryn Bryant
Total pages 116
Collection year 2005
Language eng
Subjects L
230101 Mathematical Logic, Set Theory, Lattices And Combinatorics
780101 Mathematical sciences
Formatted abstract

An embedding of a partial G-design (X, P) is a G-design (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 G-design 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 G-designs for various graphs G has received much attention in recent years, particularly for the case of partial Steiner triple systems and partial m-cycle 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 (K4 \ K2)-designs [26]. While the graph K4 \ K2 differs from K4 (a block of size 4) by only one edge, Hoffman and Lindner's embedding relies heavily on the fact that K4 \ K2 is tripartite. Since K4 is not tripartite, a small embedding for partial K4-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 G-designs 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 cycle-related graphs G. In Chapter 2, we consider the case when G is either D6 (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 K4-designs. This embedding is valid for any partial K4- design which has the property that every copy of K4 contains at least two vertices which do not occur in any other copy of K4.


The concept of irreducibility is introduced in Chapter 5, and is applied to 2- fold m-cycle systems. Specifically, it is shown that for any pair of integers (m, n) with 4 < m < n, if there exists an m-cycle system of order n, then there exists an irreducible 2-fold m-cycle 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 m-cycle systems when λ> 2. We prove the existence of irreducible 3 -fold m-cycle systems of various orders, and show that for any λ > 2, there exists an irreducible A-fold m-cycle 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 6-fold 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.

Keyword Embeddings (Mathematics)
Graphic methods

Document type: Thesis
Collection: UQ Theses (RHD) - UQ staff and students only
Citation counts: Google Scholar Search Google Scholar
Created: Fri, 24 Aug 2007, 18:45:02 EST