A set of$k$spanning trees in a graph$G$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$. The existence of multiple CISTs in the underlying graph of a network has applications in fault-tolerant broadcasting and secure message distribution. In this paper, we investigate the construction of CISTs in a server-centric data center network called BCube connected crossbars (BCCC), which can provide good network performance using inexpensive commodity off-the-shelf switches and commodity servers with only two network interface card (NIC) ports. The significant advantages of BCCC are its good expandability, lower communication latency, and higher robustness in component failure. Based on the structure of compound graphs of BCCC, we provide efficient algorithms to construct$\lceil \frac{n}{4}\rceil$CISTs in the logical graph of BCCC, denoted by$L$-$BCCC(n,k)$, for$n\geqslant 5$. As a by-product, we obtain a fault-tolerant routing that takes the constructed CISTs as its routing table. We then evaluate the performance of the fault-tolerant routing through simulation results.

A set of k (≥ 2) spanning trees in the underlying graph of a network topology is called completely independent spanning trees, (CISTs for short), if they are pairwise edge-disjoint and inner-node-disjoint. Particularly, if k=2, the two CISTs are called a dual-CIST. However, it has been proved that determining if there exists a dual-CIST in a graph is an NP-hard problem. Kwong et al. [IEEE/ACM Transactions Networking 19(5) 1543-1556, 2011] defined that a routing is protected, if there is an alternate with loop-free forwarding, when a single link or node failure occurs. Shortly afterward, Tapolcai [Optim. Lett. 7(4) 723-730, 2013] showed that a network possessing a dual-CIST suffices to establish a protection routing. It is well-known that Cayley graphs have a large number of desirable properties of interconnection networks. Although many results of constructing dual-CISTs on interconnection networks have been proposed in the literature, so far, the work has not been dealt with on Cayley graphs due to that their expansions are in exponential scalability. In this paper, we try to make a breakthrough of this work on some famous subclasses of Cayley graphs, including alternating group networks, bubble-sort network, and star networks. We first propose tree searching algorithms for helping the construction of dual-CISTs on low-dimensional networks. Then, by inductive construction, we show that dual-CISTs on high-dimensional networks can also be constructed agreeably. As a result, we can configure protection routings by using the constructed dual-CISTs. In addition, we complement some analysis with a simulation study of the proposed construction to evaluate the corresponding performance.

In this paper, we determine the wide diameters of regular hyper-stars HS(2k,k) and folded hyper-stars FHS(2k,k)⁠. We first provide a connection between the wide diameter and the maximum height of a set of particular spanning trees, called independent spanning trees (ISTs for short), of a graph. According to this relation, we analyze the heights of ISTs constructed in the previous works to establish upper bounds of the wide diameters of HS(2k,k) and FHS(2k,k)⁠. By contrast, we take the known results of fault diameters of HS(2k,k) and FHS(2k,k) as lower bounds. Consequently, we obtain the following results: (i) Dw(HS(2k,k))=2k+1 for k≥2⁠, and (ii) Dw(FHS(4,2))=3 and Dw(FHS(2k,k))=k+2 for k≥3⁠, where Dw(G) stands for the wide diameter of a graph G. The latter gives the answer of a question arisen from a previous work [(2015) Pruning longer branches of ISTs on folded hyper-stars, Comput. J., 58, 2972–2981]. In addition, we ascertain that all ISTs of HS(2k,k) and FHS(2k,k) constructed in the previous works are optimal in the sense that their heights are minimized.

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance, bandwidth and security. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. In this paper, we give an algorithm to construct ISTs on enhanced hypercubes Qn,k, which contain folded hypercubes as a subclass. Moreover, we show that these ISTs are near optimal for heights and path lengths. Let D(Qn,k) denote the diameter of Qn,k. If n - k is odd or n - k ∈ {2; n}, we show that all the heights of ISTs are equal to D(Qn,k) + 1, and thus are optimal. Otherwise, we show that each path from a node to the root in a spanning tree has length at most D(Qn,k) + 2. In particular, no more than 2.15 percent of nodes have the maximum path length. As a by-product, we improve the upper bound of wide diameter (respectively, fault diameter) of Qn,kfrom these path lengths.