Trees and subtrees
Gary Gordon, Lafayette University
About the Seminar
Trees and subtrees are ubiquitous in graph theory. We’ll consider 2 questions involving them in this talk:
- Suppose T is a tree, and let sa,b be the number of subtrees of T with a edges and b leaves. Can you reconstruct T from all the sa,b’s?
- Suppose a subtree is randomly selected from the collection of all subtrees of Kn.
What is the probability that your subtree spans Kn?
The techniques used to solve both problems are elementary, and they are connected by two different graph polynomials. We will be able to answer both questions completely in this talk.
This is joint work with Alex Chin, David Eisenstat, Kellie MacPhee, Eleanor McDonnell and Charles Vincent.