Constructing tri-CISTs in shuffle-cubes

Let T = {T-1, T-2, ..., T-k} be a set of 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, T is called a dual-CIST (resp. tri-CIST) provided k = 2 (resp. 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 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 S Q(6), and shows that the diameters of three CISTs are 22, 22, and 13. Then, by the hierarchical structure of S Q(n), we propose a recursive algorithm for constructing a tri-CIST for high-dimensional shuffle-cubes. When n >= 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.

Automated summary

Completely Independent Spanning Trees (CISTs) are a set of spanning trees used in graph theory for fault-tolerant routing and secure message distribution. A recent paper proposes an algorithm for constructing a triple CIST in a specific network structure using the CIST-partition technique. The paper also presents a recursive algorithm for constructing a triple CIST in high-dimensional networks.