TY - JOUR
T1 - Independent spanning trees in crossed cubes
AU - Cheng, Baolei
AU - Fan, Jianxi
AU - Jia, Xiaohua
AU - Zhang, Shukui
PY - 2013/6/1
Y1 - 2013/6/1
N2 - Multiple independent spanning trees (ISTs) can be used for data broadcasting in networks, which can provide advantageous performances, such as the enhancement of fault-tolerance, bandwidth, and security. However, there is a conjecture on the existence of ISTs in graphs: If a graph G is n-connected (n ≥ 1), then there are n ISTs rooted at an arbitrary vertex in G. This conjecture has remained open for n ≥ 5. The n-dimensional crossed cube CQn is a n-connected graph with various desirable properties, which is an important variant of the n-dimensional hypercube. In this paper, we study the existence and construction of ISTs in crossed cubes. We first give a proof of the existence of n ISTs rooted at an arbitrary vertex in CQn(n ≥ 1). Then, we propose an O(N log2N) constructive algorithm, where N = 2n is the number of vertices in CQn. © 2013 Elsevier Inc. All rights reserved.
AB - Multiple independent spanning trees (ISTs) can be used for data broadcasting in networks, which can provide advantageous performances, such as the enhancement of fault-tolerance, bandwidth, and security. However, there is a conjecture on the existence of ISTs in graphs: If a graph G is n-connected (n ≥ 1), then there are n ISTs rooted at an arbitrary vertex in G. This conjecture has remained open for n ≥ 5. The n-dimensional crossed cube CQn is a n-connected graph with various desirable properties, which is an important variant of the n-dimensional hypercube. In this paper, we study the existence and construction of ISTs in crossed cubes. We first give a proof of the existence of n ISTs rooted at an arbitrary vertex in CQn(n ≥ 1). Then, we propose an O(N log2N) constructive algorithm, where N = 2n is the number of vertices in CQn. © 2013 Elsevier Inc. All rights reserved.
KW - Crossed cube
KW - Fault-tolerant broadcasting
KW - Independent spanning trees
KW - Internally vertex-disjoint paths
UR - http://www.scopus.com/inward/record.url?scp=84875214715&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84875214715&origin=recordpage
U2 - 10.1016/j.ins.2013.01.010
DO - 10.1016/j.ins.2013.01.010
M3 - 21_Publication in refereed journal
VL - 233
SP - 276
EP - 289
JO - Information Sciences
JF - Information Sciences
SN - 0020-0255
ER -