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

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\in 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 \(BS_n\), 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\), \(BS_n\), \(AGN_n\) for \(n\geqslant 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 \(BS_n\) are with the same scale, we experimentally assess the performance of protection routing through simulation results for comparing them when \(n=5,6,7\).