Three completely independent spanning trees of crossed cubes with application to secure-protection routing

Kwong et al. (2011) proposed a reactive routing scheme using the multi-paths technique for integrating two mechanisms of route discovery and route maintenance in intra-domain IP networks. They further defined a route to be a protection routing if there is a loop-free alternate path for packet forwarding when a single failed component (including link or node) occurs. Later on, Tapolcai (2013) showed that a network possessing two completely independent spanning trees (CISTs for short) suffices to configure a protection routing. A set of spanning trees in a network is called CISTs if they are pairwise edge-disjoint and inner-node-disjoint. Particularly, if , such a set of CISTs is called a dual-CIST. In the early stage, Hasunuma (2002) already pointed out that the problem of determining whether there exists a dual-CIST in a graph is NP-complete. In this paper, we investigate how to construct CISTs in a kind of hypercube-variant networks, called crossed cubes, and obtain the following results: