W&M Featured Events
[PAST EVENT] Honors Thesis Defense - Merielyn Sher
Title: The Enumeration of Minimum Path Covers of Trees
Abstract:
A path cover of a tree T is a collection of induced paths of T that are vertex disjoint and cover all the vertices of T. A minimum path cover (MPC) of T is a path cover with the minimum possible number of paths, and that minimum number is called the path cover number of T. A tree can have just one or several MPC's. Prior results have established equality between the path cover number of a tree T and the largest possible multiplicity of an eigenvalue that can occur in a symmetric matrix whose graph is that tree. We hope to gain insights into the different ways that maximum multiplicity occurs among the multiplicity lists of T by enumerating its MPC's. The overall strategy is to divide and conquer. Given any tree T, several techniques are introduced to decompose T into smaller components. Then, the number of MPC's of these smaller trees can be calculated and recombined to obtain the number of MPC's for the original tree T.