Theses and Dissertations Collection

This dissertation concerns two related problems within Graph Theory. The first problem involves the packing of a graph or a set of graphs into another graph. The second problem is partitioning a graph into disjoint cycles. The main focus of this work is to present a new result in each of these areas.

Chapter 1 provides some historical context for the development and usefulness of graph problems as well as giving brief surveys on packing and partitioning of graphs. A brief summary of relevant notation is also given.

Chapter 2 contains a new contribution to the packing problem. A tree T is said to be k-placeable if it is possible to place k edge-disjoint copies of T in a complete graph of the same order. The main result of this Chapter is Theorem 2.1.1 which completely characterizes all trees that are 4-placeable and extends results which previously characterized all trees that were k placeable for k = 2 or k = 3.

Chapter 3 contains a new contribution to the partitioning problem. The main result is Theorem 3.1.1 which states that for any positive integer k, a graph G of order 7k having minimum degree at least 4k contains k disjoint cycles of length 7. This extends some similar results concerning cycles of lesser length and also lends additional support to a conjecture made by El-Zahar and (in a lesser way) Wang concerning disjoint cycles in graphs (see Conjecture 1.4.30 and Conjecture 1.4.27).