IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

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).

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC