Leafy spanning trees in hypercubes

We prove that the d-dimensional hypercube, Q(d), with n = 2(d) vertices, co ntains a spanning tree with at least (1 - 2/log(2) n - o (1/log n)) n + 2 leaves. This improves upon the bound implied by a more general result on sp anning trees in graphs with minimum degree delta, which gives (1 - O(log lo g n)/log(2) n)n as a lower bound on the maximum number of leaves in spannin g trees of n-vertex hypercubes. (C) 2001 Elsevier Science Ltd. All rights r eserved.