Extremal Trees and Reconstruction

Andrew Ray, UNL

Meeting Time: April 12, 2011, 2:00-2:50pm, Avery 347

Abstract: I will discuss two problems in graph theory. First, I will talk about finding the trees with given degree sequence that are extremal for a variety of graph 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 a common approach to all of these problems 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. Second, I will consider the problem of reconstructing graphs from metric balls of their vertices. This is an example of a reconstruction problem in which we are given limited information about a graph and decide whether the graph is uniquely determined by this data.