## Spanning Trees with Many Leaves in Hypercubes

- April 6, 2018
- 2:30 p.m.
- LeConte 312

## Abstract

Since hypercubes are used as a structure to link networks of processors, it is natural to ask what is the maximum number of leaves for any spanning tree of the n-cube graph Q_n (Bezrukov, 2014). Equivalently, we seek the minimum size of a set of vertices in Q_n that forms a connected dominating set. While an exact answer for all n (for the connected domination number) is beyond reach, we can hope to solve it asymptotically for large n. With several techniques we can now do this to within a factor of two, but it seems one more idea is needed to finish it off (if indeed there is a single answer).