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.