Senior Honor Thesis: Balanced partitions of weighted graphs: overview and a topological approach

Abstract: We study the partitioning of k-connected graphs into connected subgraphs, a problem that has notable applications in areas such as network design and power grid islanding. We first review a proof of Lovasz--Gyori Theorem, which is a modified version of the original combinatorial approach used by Gyori. This theorem states that any k-connected graph can be decomposed into k disjoint connected subgraphs, each with a prescribed number of vertices. Additionally, we provide the proof of a weighted analog in the cases of 2-connected and 3-connected graphs. We then turn into Lovasz’s method using methods of algebraic topology, summarizing his approach and providing the proof of the Lovasz--Gyori Theorem for 3-connected graphs by constructing a certain cell complex out of the spanning trees. Finally, we employ Lovasz’s approach to provide a new proof of the weighted variant for 3-connected graphs, illustrating a technique we believe can be used to address a conjecture on a weighted analog of the Lovasz-Gyori theorem