Independent spanning trees on twisted cubes

Multiple independent spanning trees have applications to fault tolerance and data broadcasting in distributed networks. There are two versions of the nn independent spanning trees conjecture. The vertex (edge) conjecture is that any nn-connected (nn-edge-connected) graph has nn vertex-independent spanning trees (edge-independent spanning trees) rooted at an arbitrary vertex. Note that the vertex conjecture implies the edge conjecture. The vertex and edge conjectures have been confirmed only for nn-connected graphs with n≤4n≤4, and they are still open for arbitrary nn-connected graph when n≥5n≥5. In this paper, we confirm the vertex conjecture (and hence also the edge conjecture) for the nn-dimensional twisted cube TQnTQn by providing an O(NlogN)O(NlogN) algorithm to construct nn vertex-independent spanning trees rooted at any vertex, where NN denotes the number of vertices in TQnTQn. Moreover, all independent spanning trees rooted at an arbitrary vertex constructed by our construction method are isomorphic and the height of each tree is n+1n+1 for any integer n≥2n≥2.

► Constructing the nn independent spanning trees (ISTs).
► Proving all the ISTs are isomorphic.
► Proving the height of all ISTs is n+1n+1.
► Providing an O(NlogN)O(NlogN) algorithm of ISTs.