Partition-good, Recursively Partitionable, and, In Between, Arbitrarily Partitionable

Abstract

Graph partitioning problems form a broad class of problems in graph theory that investigate the partitioning of a graph's vertices, edges, or both into subgraphs satisfying prescribed constraints. This dissertation has three sections, two of which concern graph partitioning and a third that emerged naturally from the investigation of the first two.

After introducing the necessary background and historical context, the dissertation further develops the theory of partition-good graphs alongside the well established theory of recursively and arbitrarily partitionable graphs. New measures of partitionability, namely the 2p-number and the web number, are introduced and investigated. The first question of this dissertation works on establishing conditions under which graphs from various classes satisfy partition-goodness and, where appropriate, characterizes conditions for recursive and arbitrary partitionability. Additional results concerning 2p-numbers and web numbers for selected graph classes are also presented when discussing this question. The second question question studied examines under what conditions two disjoint graphs, one traceable and the other connected, may be joined by a single edge such that the resultant graph is partition-good.

Finally, motivated by the investigations of the first two sections, the dissertation addresses the enumeration of isomorphism classes of spanning trees of complete bipartite graphs.