Constructing Tri-CISTs in Shuffle-Cubes

A set of spanning trees \(\mathcal {T}=\{T_1,T_2,\dots ,T_k\}\) with \(k\geqslant 2\) in a graph G is called completely independent spanning trees (CISTs for short) if the paths joining every pair of vertices x and y in any two trees have neither vertex nor edge in common except for x and y. Particularly, \(\mathcal {T}\) is called a dual-CIST (resp. tri-CIST) provided \(k=2\) (resp. \(k=3\)). Recently, the construction of a dual-CIST has been proposed in a shuffle-cube \(SQ_n\), which is an innovative hypercube-variant network that possesses both short diameter and connectivity advantages. This paper uses the CIST-partition technique to construct a tri-CIST of \(SQ_6\), and shows that the diameters of three CISTs are 22, 22, and 13. Then, by the hierarchical structure of \(SQ_n\), we propose a recursive algorithm for constructing a tri-CIST for high-dimensional shuffle-cubes. When \(n\geqslant 10\), the diameters of \(T_i\), \(i=1,2,3\), we constructed for \(SQ_n\) are as follows: \(2n+11\), \(2n+9\), and \(2n+1\).