Constructive Algorithm of Independent Spanning Trees on Mobius Cubes
Baolei Cheng, Jianxi Fan, Xiaohua Jia, S. Zhang, B. Chen · The Computer Journal · 2012
Independent spanning trees (ISTs) on networks have applications in networks such as reliable communication protocols, the multi-node broadcasting, one-to-all broadcasting, reliable broadcasting and secure message distribution. However, there is a problem on ISTs on graphs: If a graph G is n-connected (n ≥ 1), then there are n ISTs rooted at an arbitrary vertex on G. This problem has remained open for n ≥ 5. In this paper, we consider the construction of ISTs on Möbius cubes—a class of hypercube variants. An O(N log N) recursive algorithm is proposed to construct n ISTs rooted at an arbitrary vertex on the n-dimensional Möbius cube Mn, where N = 2n is the number of vertices in Mn. Furthermore, we prove that each IST obtained by our algorithm is isomorphic to an n-level binomial-like tree with the height n + 1 for n ≥ 2.