Leafy spanning trees in hypercubes
✍
W. Duckworth; P.E. Dunne; A.M. Gibbons; M. Zito
📂
Article
📅
2001
🏛
Elsevier Science
🌐
English
⚖ 214 KB
We prove that the d-dimensional hypercube, Qd, with n ----2 d vertices, contains a spanning tree with at least 1 log 2 n o n -t-2 leaves. This improves upon the bound implied by a more general result on spanning trees in graphs with minimum degree 5, which gives (1 -O(loglogn)/log 2 n)n as a lower b