Search

Multiple edge-disjoint Hamiltonian cycles (EDHCs) provide the advantages of data broadcast in parallel and edge fault-tolerance in network communications. This paper investigates how to construct more EDHCs in a hypercube-variant network called crossed cube, denoted as C Q n . The topology of C Q n has more wealth than normal hypercubes in network properties, e.g., it has about half of the diameter of a hypercube with the same dimension. Then, we obtain the following results in this paper: (1) We first provide the construction of three EDHCs in C Q 6 . (2) According to the recursive structure of C Q n , we prove by induction that there exist also three EDHCs in C Q n for n ⩾ 7 . (3) Finally, we evaluate the performance of data broadcasting by simulation through three EDHCs and compare it against the best previous result in [18] using two EDHCs. In particular, our findings significantly improved the average success rate in edge fault-tolerant data broadcasting and two specific metrics concerning the broadcasting delivery time (latency). [ABSTRACT FROM AUTHOR]

Let T = { T 1 , T 2 , ... , T k } be a set of k ⩾ 2 spanning trees in a graph G. The k spanning trees 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. Particularly, T is called a dual-CIST (resp. tri-CIST) provided k = 2 (resp. k = 3 ). From an algorithmic point of view, the problem of finding a dual-CIST in a given graph is known to be NP-hard. For data transmission applications in reliable networks, the existence of a dual-CIST can provide a configuration of fault-tolerant routing called protection routing. The presence of a tri-CIST can enhance the dependability of transmission and carry out secure message distribution for confidentiality. Recently, the construction of a dual-CIST has been proposed in a shuffle-cube S Q n , which is an innovative hypercube-variant network that possesses both short diameter and connectivity advantages. This paper uses the CIST-partition technique to construct a tri-CIST of S Q 6 , and shows that the diameters of three CISTs are 22, 22, and 13. Then, by the hierarchical structure of S Q n , we propose a recursive algorithm for constructing a tri-CIST for high-dimensional shuffle-cubes. When n ⩾ 10 , the diameters of T i , i = 1 , 2 , 3 , we constructed for S Q n are as follows: 2 n + 11 , 2 n + 9 , and 2 n + 1 . [ABSTRACT FROM AUTHOR]

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 ∈ 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 B S n , pancake graph P n , alternating group networks A G N 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 , B S n , A G N 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 B S 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 . [ABSTRACT FROM AUTHOR]

A set of spanning trees in a graph G is called independent spanning trees (ISTs for short) if they are rooted at the same vertex, say r, and for each vertex v (≠ r) in G, the two paths from v to r in any two trees share no common edge and no common vertex except for v and r. Constructing ISTs has applications on fault-tolerant broadcasting and secure message distribution in reliable communication networks. Since Cayley graphs have been used extensively to design the topologies of interconnection networks, construction of ISTs on Cayley graphs is significative. It is well-known that star networks S n and bubble-sort network B n are two of the most attractive subclasses of Cayley graphs. Although it has been dealt with about two decades for the construction of ISTs on S n (which has been pointed out that there is a flaw and has been corrected recently), so far the problem of constructing ISTs on B n is not dealt with yet. In this paper, we present an algorithm to construct n - 1 ISTs of B n . Moreover, we show that our algorithm has amortized efficiency for multiple trees construction. In particular, every vertex can determine its parent in each spanning tree in a constant amortized time. Accordingly, except for the star networks, it seems that our work is the latest breakthrough on the problem of ISTs for all subfamilies of Cayley graphs. [ABSTRACT FROM AUTHOR]