Physical Sciences and Mathematics Commons^™

Packings And Realizations Of Degree Sequences With Specified Substructures, Tyler Seacrest

Department of Mathematics: Dissertations, Theses, and Student Research

This dissertation focuses on the intersection of two classical and fundamental areas in graph theory: graph packing and degree sequences. The question of packing degree sequences lies naturally in this intersection, asking when degree sequences have edge-disjoint realizations on the same vertex set. The most significant result in this area is Kundu's k-Factor Theorem, which characterizes when a degree sequence packs with a constant sequence. We prove a series of results in this spirit, and we particularly search for realizations of degree sequences with edge-disjoint 1-factors.

Perhaps the most fundamental result in degree sequence theory is the Erdos-Gallai Theorem, characterizing …