Formatted abstract

In recent years much work has been done on finding edgedisjoint decompositions of a complete graph on v vertices, K_{ν}, into copies of certain graphs. In particular, the problem of finding decompositions of complete graphs into cycles of length n, Cn, has received much attention, and this problem was solved for many cases by Kotzig, Rosa, Hoffman, Lindner and Rodger. Recently, the necessary conditions for the existence of a decomposition of the complete graph into cycles of a fixed length have been shown to be sufficient by Alspach, Gavlas and Sajna. For any graph G the set of values of v for which there exists a Gdecomposition of Kν (also called a Gdesign of order v) is called the spectrum for Gdesigns.
In this thesis we consider the spectrum problem for certain theta graphs. A theta graph is a simple graph consisting of two vertices joined by a number of internally disjoint paths, and we denote it here by θ(l_{1},l_{2},…,l_{t}), where l_{1},l_{2},…,l_{t} are the lengths of the paths. This notation for theta graphs was introduced by Loerinc in 1978. As an example, K_{4} — e, a complete graph on four vertices missing one edge, is a theta graph consisting of four vertices, with two vertices joined by one path of length one and two paths of length two, denoted by θ ( 1 , 2, 2). Moreover, note that the graphs K_{m+2} \ K_{m} constitute a family of theta graphs, θ (1, 2, 2 , . . . , 2). Many properties of the graph K_{4} — e (and also the graphs K_{m+2} \ K_{m}) have been investigated. Also, the graphs K2,m form another family of theta graphs, θ (2, 2 , . . . , 2). The spectrum problem for theta graphs consisting of three paths will be the focus of much of this thesis. Theta graphs of the form θ (l_{1},l_{2},l_{3}) may be thought of as an edgeamalgamation of two cycles of length l_{i} + l_{j }and l_{i} + l_{k}, with l_{i} edges in common, where (i,j, k) is some permutation of (1,2,3). Continuing with the previous example, θ (1, 2, 2) may be thought of as an amalgamation of two cycles of length three, with one edge in common.
Unlike cycle designs, the obvious necessary conditions for the existence of a theta graph design are not always sufficient; and this lack of sufficiency in certain cases is investigated in Chapter 2.
In Chapters 3, 4 and 5 we complete the spectrum problem for theta graphs with fewer than ten edges. Many of the necessary examples (which appear in Appendix A) used these in chapters were found using autogen, a graph decomposition software package written by Adams.
A decomposition of K_{ν}\L, the complete graph of order v with the edges of a subgraph L (called the leave) removed, into edge disjoint copies of a graph G is called a maximum packing of Kν with G if L contains as few edges as possible. A decomposition of K_{ν} U X with V(X) C V(K_{ν}), the complete graph of order v union a graph X (called the excess), into edge disjoint copies of a graph G is called a minimum covering of K_{ν} with G if X contains as few edges as possible. The maximum packing and minimum covering problems have been studied for many graphs. In Chapter 6 we construct maximum packings and minimum coverings of K_{ν} with copies of θ (1,3,3) for all ν‡ 0 or 1 (mod 7), where L and X are compact (that is, are simple graphs on the least number of vertices). The necessary examples required for the constructions given in this chapter can be found in Appendix B. (When ν = 0 or 1 (mod 7), the leave or excess is empty, and a decomposition of K_{ν}_{ }in this case into θ(1,3,3) is covered by the results of Chapter 3.)
In Chapters 7, 8 and 9 we present some general constructions for theta graph decompositions. In Chapter 7, methods for decomposing the complete graph K_{ν} into theta graphs of the form θ(1, n, n) are given when ν Ξ 0(mod 2n + 1) if n is odd, and when ν Ξ 1 (mod 2n + 1) if n Ξ 3 (mod 4); in the case n Ξ 1 (mod 4) further partial results are obtained. In Chapter 8, methods for decomposing the complete graph Kν into theta graphs of the form θ(1, n, n) are given when ν Ξ l (mod 2n I1) and n Ξ 2 (mod 4). In Chapter 9, methods for decomposing the complete graph Kν into theta graphs of the form θ(1, 2m, 2n  2m) are given when νΞ2n + 1, 2n +2,4n + 3, 6n + 3,6n + 4 (mod 8n + 4) and n is odd.
For any graph G, an injective function h : V(G) > N is called a labelling (or a valuation) of G. In 1966, Rosa introduced a hierarchy of labellings, including ρ, β and αlabellings. In Chapters 10 and 11 some new types of labellings are added to this hierarchy. The concept of an ordered ρlabelling (denoted ρ^{+}) was introduced by ElZanati, Vanden Eynden and Punnim. As with the case of an αlabelling, a ρ^{+}labelling of a graph G with n edges yields a cyclic Gdecomposition of K_{2nx+1} for all positive integers χ. It was shown by ElZanati et al. that the disjoint union of a collection of graphs with αlabellings has a p^{+}labelling. In Chapter 10 we show that the disjoint union of a collection of graphs with αlabellings together with a graph with a slightly restricted ρ^{+}labelling (called a p^{++}labelling) also has a p^{++}labelling. This result has an application to the cyclic decomposition of certain complete graphs into the disjoint union of evenlength cycles.
An almostbipartite graph is a nonbipartite graph with the property that the removal of a (possibly particular) single edge renders the graph bipartite. Examples of such graphs include odd cycles and the graphs K_{m+2 }\ K_{m}. The technique of labelling the vertices of bipartite graphs to yield decompositions of certain complete graphs has received much attention in the literature. In Chapter 11 we introduce the concept of a γlabelling of an almostbipartite graph and show that if an almostbipartite graph G with n edges has a γlabelling then there is a cyclic Gdecomposition of K_{2nx+1} for all positive integers x. We show that odd cycles and certain other almostbipartite graphs have γlabellings.
In Chapter 12, we combine the results concerning theta graph designs with the results concerning the labelling of the vertices of graphs by giving αlabellings of some bipartite theta graphs and 7labellings of some almostbipartite theta graphs.
In Chapter 13, a small result concerning Eulerian circuits and the regular icosahedron is presented.
Finally, in Chapter 14 we summarise the results of this thesis.
