Constructing dual-CISTs of pancake graphs and performance assessment of protection routings on some Cayley networks

Abstract

For a connected graph G = (V, E), two spanning trees T-1 and T-2 of G are said to be a pair of completely independent spanning trees (or a dual-CIST for short) if for any two vertices u, v is an element of V, the paths joining u and v in the two trees have no common vertex except for u and v. Although the existence of a dual-CIST in the underlying graph of a network has the practical application of protection routing on fault-tolerance, it has been proved that determining whether a graph G admits a dual-CIST is NP-complete. As we know that Cayley graphs are a large family of graphs, some of its subclasses have been attracted and thus graphs in these subclasses have been adopted as the topologies of interconnection networks, such as the n-dimensional star graphs S n, bubble sort graphs BSn, pancake graph P n, alternating group networks AGN(n) and so on. Pai and Chang (IEEE/ACM Trans Netw 27(3): 1112-1123, 2019) recently showed that there exist dual-CISTs in S-n, BSn, AGN(n) for n >= 5 and provided their corresponding protection routings. So far, the problem of constructing dual-CISTs on P-n has not been dealt with yet. In this sequel, we continue the investigation of the construction of dual-CISTs in pancake graphs as a complementary result. Since P-n, S-n, and BSn are with the same scale, we experimentally assess the performance of protection routing through simulation results for comparing them when n = 5, 6, 7.