Spanning trees with many leaves in hypercubes
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 Qn (Bezrukov, 2014). Equivalently, we seek the minimum size of a set of vertices in Qn 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. Still, we hope to understand better the problem of domination in hypercubes.