TY - JOUR
T1 - Constructive algorithm of independent spanning trees on möbius cubes
AU - Cheng, Baolei
AU - Fan, Jianxi
AU - Jia, Xiaohua
AU - Zhang, Shukui
AU - Chen, Bangrui
PY - 2013/11
Y1 - 2013/11
N2 - 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.
AB - 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.
KW - Binomial-like tree
KW - Independent spanning tree
KW - Internally vertex-disjoint path
KW - Möbius cube
UR - http://www.scopus.com/inward/record.url?scp=84872445123&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84872445123&origin=recordpage
U2 - 10.1093/comjnl/bxs123
DO - 10.1093/comjnl/bxs123
M3 - RGC 21 - Publication in refereed journal
VL - 56
SP - 1347
EP - 1362
JO - Computer Journal
JF - Computer Journal
SN - 0010-4620
IS - 11
ER -