Embedding double starlike trees into hypercubes

Abstract

A�double starlike tree�is a subdivision of a double star where the edge joining the central vertices is not subdivided. It was conjectured and subsequently proved by Kobeissi and Mollard [M. Kobeissi and M. Mollard,�Spanning graphs of hypercubes: Starlike and double starlike trees, Discrete Math. 244 (2002), pp. 231�239; M. Kobeissi and M. Mollard,�Disjoint cycles and spanning graphs of hypercubes, Discrete Math. 288 (2004), pp. 73�87]. that every equipartite double starlike tree on 2�n�vertices with maximum degree at most�n�spans the hypercube of dimension�n. In this note, we present an alternative and simple proof of this theorem using our results proved recently in Choudum�et al. [S.A. Choudum, S. Lavanya and V. Sunitha,�Disjoint paths in hypercubes with prescribed origins and lengths, Int. J. Comput. Math. 87 (2010), pp. 1692�1708].