Extremal trees and reconstruction

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, related to, but not the same as, the original invariant. We exploit the recursive structure of the problem. The second approach is geared towards finding the trees with given degree sequence that are extremal. I have a common approach involving labelings of the vertices corresponding to each invariant; the canonical example of which is labeling the vertices by the components of the leading eigenvector. This approach yields strictly stronger results when combined with a majorization result. Second, I will consider two problems in graphs reconstruction. For these problems we are given limited information about a graph and decide whether the graph is uniquely determined by this data. The first problem is reconstruction of trees from their k-subtree matrix; a generalization of the Wiener matrix. This includes the problem of reconstruction from the Wiener matrix which was an open problem. Two vertices are adjacent if the corresponding entry is the largest in either its row or its column. The second problem is reconstructing graphs from metric balls of their vertices. I give a solution to the conjecture that every graph with no pendant vertices and girth at least 2r + 3 can be reconstructed from its metric balls of radius r. We do so by examining the intersections of metric balls and their sizes