Construction of independent spanning trees on twisted-cubes
Yan Wang, Jianxi Fan, Yuejuan Han · 2011
Multiple independent spanning trees have applications to fault-tolerant and data broadcasting in distributed networks. There is a conjecture on independent spanning trees: any n-connected graph has n independent spanning trees rooted at an arbitrary vertex. The conjecture has been confirmed only for n-connected graphs with n ≤ 4, and still open for arbitrary n-connected graphs when n ≥ 5. In this paper, we confirm the conjecture for the n-dimensional twisted-cube TNnby providing an O(NlogN) algorithm to construct n independent spanning trees rooted at any vertex, where N denotes the number of vertices in TNn.