Spanning Trees and Domination in Hypercubes

Jerrold R. Griggs

paper

Spanning Trees and Domination in Hypercubes

arXiv:1905.13292

Abstract

Let $L (G)$ denote the maximum number of leaves in any spanning tree of a connected graph $G$ . We show the (known) result that for the $n$ -cube $Q_{n}$ , $L (Q_{n}) \sim 2^{n} = ∣ V (Q_{n}) ∣$ as $n \to \infty$ . Examining this more carefully, consider the minimum size of a connected dominating set of vertices $γ_{c} (Q_{n})$ , which is $2^{n} - L (Q_{n})$ for $n \geq 2$ . We show that $γ_{c} (Q_{n}) \sim 2^{n} / n$ . We use Hamming codes and an "expansion" method to construct leafy spanning trees in $Q_{n}$ .