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

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 SQ(n) with n = 4k + 2 and k >= 1. Furthermore, recursive construction algorithms for the dual-CIST in SQ(n) are given. (C) 2021 Elsevier Inc. All rights reserved.

Automated summary

The article discusses the existence of completely independent spanning trees in a graph, focusing on the concept of dual CIST and its applications in data transmission and protection routing. It is mentioned that determining the existence of dual CIST in a graph is NP-complete, and the presence of dual CIST in n-dimensional shuffle-cubes is proven with recursive construction algorithms provided.