Constructing tri-CISTs in shuffle-cubes

Let $${\mathcal {T}}=\{T_1,T_2,\ldots ,T_k\}$$ T = { T 1 , T 2 , … , T k } be a set of $$k\geqslant 2$$ k ⩾ 2 spanning trees in a graph G. The k spanning trees are 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}}$$ T is called a dual-CIST (resp. tri-CIST) provided $$k=2$$ k = 2 (resp. $$k=3$$ k = 3 ). From an algorithmic point of view, the problem of finding a dual-CIST in a given graph is known to be NP-hard. For data transmission applications in reliable networks, the existence of a dual-CIST can provide a configuration of fault-tolerant routing called protection routing. The presence of a tri-CIST can enhance the dependability of transmission and carry out secure message distribution for confidentiality. Recently, the construction of a dual-CIST has been proposed in a shuffle-cube $$SQ_n$$ S Q 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$$ S Q 6 , and shows that the diameters of three CISTs are 22, 22, and 13. Then, by the hierarchical structure of $$SQ_n$$ S Q n , we propose a recursive algorithm for constructing a tri-CIST for high-dimensional shuffle-cubes. When $$n\geqslant 10$$ n ⩾ 10 , the diameters of $$T_i$$ T i , $$i=1,2,3$$ i = 1 , 2 , 3 , we constructed for $$SQ_n$$ S Q n are as follows: $$2n+11$$ 2 n + 11 , $$2n+9$$ 2 n + 9 , and $$2n+1$$ 2 n + 1 .