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 n n independent spanning trees conjecture. The vertex (edge) conjecture is that any n n -connected (n n -edge-connected) graph has n n 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 n n -connected graphs with n?4 n ? 4 , and they are still open for arbitrary n n -connected graph when n?5 n ? 5 . In this paper, we confirm the vertex conjecture (and hence also the edge conjecture) for the n n -dimensional twisted cube TQn T Q n by providing an O(NlogN) O ( N log N ) algorithm to construct n n vertex-independent spanning trees rooted at any vertex, where N N denotes the number of vertices in TQn T Q n . 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+1 n + 1 for any integer n?2 n ? 2 .
independent spanning tree twisted cube fault tolerance broadcasting