Embedding Starlike Trees into Hypercube-Like Interconnection Networks

摘要

A starlike tree (or a quasistar) is a subdivision of a star tree. A family of hypercube-like interconnection networks called restricted HL-graphs includes many interconnection networks proposed in the literature such as twisted cubes, crossed cubes, multiply twisted cubes, Moebius cubes, Mcubes, and generalized twisted cubes. We show in this paper that every starlike tree of degree at most m with 2~m vertices is a spanning tree of m-dimensional restricted HL-graphs.