Reliability analysis based on the dual-CIST in shuffle-cubes

Abstract Let T 1 , T 2 , … , T k be k spanning trees of the graph G . They 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 . In particular, two CISTs are called a dual-CIST. The construction of a dual-CIST in a network has applications in the fault-tolerance of data transmission and the establishment of a protection routing. It has been proved that determining if a graph G admits a dual-CIST is NP-complete. In this paper, we show the existence of a dual-CIST in the n -dimensional shuffle-cube S Q n with n = 4 k + 2 and k ≥ 1 . Furthermore, recursive construction algorithms for the dual-CIST in S Q n are given.