Education Commons^™

Extremal Trees And Reconstruction, Andrew Ray

Department of Mathematics: Dissertations, Theses, and Student Research

Problems in two areas of graph theory will be considered.

First, I will consider extremal problems for trees. In these questions we examine the trees that maximize or minimize various invariants. For instance the number of independent sets, the number of matchings, the number of subtrees, the sum of pairwise distances, the spectral radius, and the number of homomorphisms to a fixed graph. I have two general approaches to these problems. To find the extremal trees in the collection of trees on n vertices with a fixed degree bound I use the certificate method. The certificate is a branch invariant, …

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 …