Constructing Independent Spanning Trees for Hypercubes and Locally Twisted Cubes

Multiple independent spanning trees (ISTs) have applications to fault-tolerant and data broadcasting in interconnections. Thus the designs of multiple ISTs in several classes of networks have been widely investigated. There are two versions of the n ISTs conjecture. The vertex (edge) conjecture is that any n-connected (n-edge-connected) graph has n vertex-ISTs (edge-ISTs) rooted at an arbitrary vertex r. Note that the vertex conjecture implies the edge conjecture. Recently, Hsieh and Tu proposed an algorithm to construct -ISTs rooted at vertex 0 for the n-dimensional locally twisted cube (LTQ_n), which is a variant of the ndimensional hypercube (Q_n). Since LTQ_n is not vertextransitive, Hsieh and Tu´s result does not solve the edge conjecture for LTQ_n. In the paper, we confirm the vertex conjecture (and hence also the edge conjecture) for LTQ_n by proposing an algorithm to construct n vertex-ISTs rooted at any vertex. We also confirm the vertex (and also the edge) conjecture for Q_n. To the best of our knowledge, our algorithm is the first algorithm that can construct n vertexISTs rooted at any vertex for both LTQ_n and Q_n.