@article{e9ae329f10d745e0a4578e0acf58c5c5, title = "Constructive algorithm of independent spanning trees on m{\"o}bius cubes", abstract = "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 Mobius 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 Mobius cube M-n, where N=2(n) is the number of vertices in M-n. 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.", keywords = "Binomial-like tree, Independent spanning tree, Internally vertex-disjoint path, M{\"o}bius cube", author = "Baolei Cheng and Jianxi Fan and Xiaohua Jia and Shukui Zhang and Bangrui Chen", year = "2013", month = nov, doi = "10.1093/comjnl/bxs123", language = "English", volume = "56", pages = "1347--1362", journal = "Computer Journal", issn = "0010-4620", publisher = "Oxford University Press", number = "11", }