A comment on “Independent spanning trees in crossed cubes”

•We point out that a previous result does not really solve the IST problem in CQnCQn.•We provide an alternative scheme for solving the IST problem in CQnCQn.•The algorithm can be parallelized to run in O(n)O(n) time using 2n2n processors.

A set of spanning trees in a graph is said to be independent (ISTs for short) if all the trees are rooted at the same node r and for any other node v  (≠r)(≠r), the paths from v to r in any two trees are node-disjoint except the two end nodes v and r. For an n-connected graph, the independent spanning trees problem asks to construct n ISTs rooted at an arbitrary node of the graph. Recently, Zhang et al. (2013) [18] proposed an algorithm to construct n ISTs with a common root at node 0 in an n  -dimensional crossed cube CQnCQn. However, it has been proved by Kulasinghe and Bettayeb (1995) [13] that the CQnCQn (a synonym called multiply-twisted hypercube in that paper) fails to be node-transitive for n⩾5n⩾5. Thus, the result of Zhang et al. does not really solve the ISTs problem in CQnCQn. In this paper, we revisit the problem of constructing n   ISTs rooted at an arbitrary node in CQnCQn. As a consequence, we show that the proposed algorithm can be parallelized to run in O(log⁡N)O(log⁡N) time using N=2nN=2n nodes of CQnCQn as processors.