Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Education
Extremal Trees And Reconstruction, Andrew Ray
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, …