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 n edge-ISTs rooted at vertex 0 for the n-dimensional locally twisted cube (LTQ_n), which is a variant of the n-dimensional hypercube (Q_n)- Since LTQ_n is not vertex-transitive, 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 vertex-ISTs roofed at any vertex for both LTQ_n and Q_n.