SOME SMALL-SIZED SPANNING SUBGRAPHS OF A HYPERCUBE

The integral of a tree T is the tree obtained by joining one new leaf to each node of T. The broadcast tree B-n is the n(th) iterated integr al of the graph K-1 consisting of just one node. We derive the number of embeddings of B-n in the hypercube Q(n). We also determine the mini mum diameter of a spanning tree of Q(n). A special spanning subgraph R -n of Q(n) is then constructed by suitably joining two broadcast trees B-n and Bn-1. This cubical graph R-n of diameter n serves to prove th at asymptotically almost all the edges of Q(n) can be removed and stil l the remaining spanning subgraph has diameter n. Other properties of this new family of graphs are investigated.