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 ⁿ 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].

Keywords:

• interconnection network
• hypercube
• embedding
• double starlike trees
• vertex disjoint paths

2010 AMS Subject Classifications :

• 05C05
• 05C10
• 05C38
• 68R10

Acknowledgements

The authors thank the referees for their various suggestions to improve the presentation. The second author thanks CSIR, India, for their financial support to this research.